简介一份基于C语言实现的迷宫创建与最短路径求解项目面向正在学习C语言、数据结构与算法的开发者尤其是想通过动手实践串联知识点的人群。资源采用C/C混合编写共13个文件压缩包仅81KB包含2个头文件、2个C源文件、可执行程序、界面图标、提示音wav及项目配置文件既有完整源码又可直接运行体验。实现上涵盖随机迷宫生成与最短路径求解两大模块支持用户自定义迷宫布局可应用深度优先搜索生成迷宫结合BFS或Dijkstra/A*思想完成路径搜索并利用栈、队列等数据结构辅助处理。项目还提供简单的文本交互界面附带了工程配置和资源文件结构清晰便于对照学习。目前已有111人学习下载适合用于课程设计、编程练习或算法入门能帮助读者理解图论与搜索算法在实际问题中的应用。1. 用C语言做迷宫最短路径先把迷宫当成一张“无权图”不少人在学习 C 语言时都动过写“迷宫游戏”的念头真动手才发现难的不是画墙和移动光标而是让程序在用户随手创建的迷宫里找到最短路径。递归深搜能“找到路”但找到的不一定最短真正可靠的做法是广度优先搜索BFS把整个迷宫看成一张无权图每个格子是一个顶点相邻的可走格子之间连一条权值为 1 的边。BFS 按层展开第一次到达终点时走过的层数天然就是最短步数。这篇文章就用纯 C 实现一遍完整流程用户自己创建迷宫、程序校验合法性、BFS 求解、路径回溯输出、以及几个后续优化思路。全程不依赖第三方库适合想在 C 语言里夯实结构体、指针、队列和图遍历的读者也适合把它当c语言游戏代码练手项目来扩展。2. 创建迷宫前先定数据结构C语言里怎么存墙和路2.1 用二维数组加结构体而不是散落的全局变量迷宫本质是一个矩形网格最自然的存储方式是二维数组。数组元素只表达“墙 / 路 / 起点 / 终点”四种状态状态用枚举或宏常量定义。直接用裸二维数组加一堆全局变量也能跑但迷宫的长宽、地图数据、起点终点坐标散落在不同变量里后面做BFS、回溯、二次编辑都非常别扭。我一般会定义一个结构体把地图相关的东西打包#define MAX_ROW 32 #define MAX_COL 32 #define CELL_WALL 0 #define CELL_ROAD 1 #define CELL_START 2 #define CELL_END 3 typedef struct { int map[MAX_ROW][MAX_COL]; // 地图数据 int rows, cols; // 实际行数、列数 int start_row, start_col; // 起点坐标 int end_row, end_col; // 终点坐标 } Maze;这里把地图数据、维度、起点终点都收进Maze。后续函数传参只传一个Maze *指针避免函数签名里带着两三个数组参数。值得提醒的是map用定长二维数组MAX_ROW * MAX_COL是为了省去动态分配内存的麻烦如果你的迷宫尺寸是运行时才确定的就把map改成int **map在创建迷宫时用malloc逐行分配。提示结构体里的定长二维数组在栈上占用32 * 32 * 4 ≈ 4KB对一般 MCU 或桌面程序都够用迷宫超过 32x32 时再考虑堆分配。2.2 方向数组把“上下左右走一步”变成坐标加减法路径搜索里最频繁的操作是从当前格子往四个方向试探。如果写成四个if判断行列增减代码会冗余且容易漏方向。常见做法是用方向数组统一表达“下一步坐标 当前坐标 方向偏移”// 上、下、左、右四个方向的行列偏移 int dirs[4][2] { {-1, 0}, // 上行减 1 { 1, 0}, // 下行加 1 { 0, -1}, // 左列减 1 { 0, 1} // 右列加 1 };在 BFS 主体里扩展下一个格子就变成int nr cur_row dirs[i][0]; int nc cur_col dirs[i][1];用dirs数组的好处是新增斜向移动时只需加两个方向项比如{-1, -1}表示左上不用改动任何业务逻辑代码。方向顺序会影响搜索结果中同等长度路径的偏向性但对“最短路径长度”本身没有影响。若希望输出路径更贴近“先往上走”的习惯把up放在数组首位即可。2.3 二维数组传参的三个写法别在函数签名上踩坑新手最常卡住的地方是“如何把 Maze 里的 map 传给一个处理函数”。map是二维数组函数形参不能直接写成int map[][]。常见的可行写法有三种形参写法适用场景说明void f(Maze *maze)对完整迷宫做操作推荐结构体把维度一起带过去void f(int map[MAX_ROW][MAX_COL], int rows, int cols)只处理地图需要同时传行数列数void f(int **map, int rows, int cols)map 是动态分配的二维数组需要先分配好每行指针如果坚持把Maze.map当int **传编译器会直接报警告因为定长二维数组与int **的内存布局不兼容。int map[4][4]的数组名指向“四个长度为 4 的 int 数组”解引用得到第 0 行数组而int **解引用得到int *语义完全不同。解决办法很简单要么整体传Maze *要么把map定义成int **并用malloc逐行分配。对于“支持用户创建迷宫”的需求整体传Maze *是最省心的校验、保存、加载、BFS 全部走同一个指针。3. 交互式创建迷宫命令行录入、合法性校验与文件读写3.1 让用户逐行输入地图程序即时反馈渲染结果创建迷宫最常见的交互方式是程序先询问行数和列数再让用户逐行输入由0和1组成的字符串可以额外约定S表示起点、E表示终点。得到原始字符串后把它转成Maze.map里的整型状态。逐行检查的好处是能当场指出格式错误避免整个地图录入完才发现中间某行少了一个字符。void createMaze(Maze *maze) { printf(请输入迷宫行数和列数用空格分隔: ); scanf(%d %d, maze-rows, maze-cols); printf(请输入 %d 行地图每行 %d 个字符\n, maze-rows, maze-cols); printf(0墙 1路 S起点 E终点\n); char line[128]; for (int r 0; r maze-rows; r) { scanf(%s, line); if (strlen(line) ! maze-cols) { printf(第 %d 行长度不是 %d请重新输入\n, r 1, maze-cols); r--; // 回退一行 continue; } for (int c 0; c maze-cols; c) { switch (line[c]) { case 0: maze-map[r][c] CELL_WALL; break; case 1: maze-map[r][c] CELL_ROAD; break; case S: case s: maze-map[r][c] CELL_START; maze-start_row r; maze-start_col c; break; case E: case e: maze-map[r][c] CELL_END; maze-end_row r; maze-end_col c; break; default: printf(第 %d 行第 %d 列字符非法%c\n, r 1, c 1, line[c]); r--; c maze-cols; // 跳过当前行剩余字符 } } } printMaze(maze); }代码里对非法行做了“回退一行”处理。r--让外层循环重新执行当前行c maze-cols则跳出内层循环。这里输入格式固定是“字符串”而不是“空格分隔的数字”就是为了减少用户录入成本。调试时自己手工敲迷宫很烦可以提前准备几行样例文本直接复制进终端。实际项目里如果要做成c语言大作业交出去还可以加一个“随机生成迷宫”选项用随机数决定每个格子是墙还是路再用checkMaze保证起点终点连通。3.2 合法性校验必须同时检查边界、状态和连通性用户手工输入最容易出现三类问题地图里没有起点或终点、起点终点重合、起点终点被墙包围导致永远走不通。前两类可以用状态统计解决第三类需要借助一个 DFS 或 BFS 做连通性探测。校验函数放在createMaze之后、BFS 之前执行避免程序“跑着跑着发现无路可走”。int checkMaze(Maze *maze) { int start_cnt 0, end_cnt 0; for (int r 0; r maze-rows; r) { for (int c 0; c maze-cols; c) { if (maze-map[r][c] CELL_START) start_cnt; if (maze-map[r][c] CELL_END) end_cnt; } } if (start_cnt ! 1 || end_cnt ! 1) { printf(迷宫必须包含且仅包含一个起点和一个终点\n); return 0; } if (maze-start_row maze-end_row maze-start_col maze-end_col) { printf(起点和终点不能重合\n); return 0; } // 连通性检测从起点做一次 DFS看能否到达终点 int visited[MAX_ROW][MAX_COL] {0}; return dfsReachable(maze, maze-start_row, maze-start_col, maze-end_row, maze-end_col, visited); }dfsReachable只管“能不能到”不负责记路径因此不需要回溯清空 visited代码也非常短四个方向依次试探遇到路就继续递归。这里用 DFS 而不是 BFS 做连通性是合理的因为只关心是否存在路径不关心路径长度。校验通过后迷宫数据才算真正可用。3.3 文件读写把创建好的迷宫存成关卡下次直接加载“支持自己创建迷宫”只停留在内存里不持久化总感觉少了点什么。加上存档功能后用户辛苦搭好的迷宫可以直接存成文本文件下次启动程序时加载继续玩。文件格式就用和输入一致的文本加载逻辑就能复用创建逻辑里的字符串解析部分。void saveMaze(Maze *maze, const char *filename) { FILE *fp fopen(filename, w); if (!fp) { perror(无法打开文件); return; } fprintf(fp, %d %d\n, maze-rows, maze-cols); for (int r 0; r maze-rows; r) { for (int c 0; c maze-cols; c) { switch (maze-map[r][c]) { case CELL_WALL: fputc(0, fp); break; case CELL_ROAD: fputc(1, fp); break; case CELL_START: fputc(S, fp); break; case CELL_END: fputc(E, fp); break; } } fputc(\n, fp); } fclose(fp); printf(迷宫已保存到 %s\n, filename); }加载函数loadMaze与saveMaze完全对称先用fscanf读行列数再逐行读字符串并按相同规则解析。文件读写操作在 C 语言里最容易出的问题是忘记fclose造成数据没落盘。另一个隐患是地图里有空格或换行符残留用fgets读行时要把末尾的\n手动去掉否则 map 最后一行会多出一个非法字符。存档文件最好和程序放在同一目录路径参数用命令行传入例如./maze solve mymap.txt这样连“加载迷宫”和“求解迷宫”两个动作都用一个入口完成。4. BFS求最短路径复用队列、前驱数组与路径回溯4.1 为什么 BFS 在“迷宫最短路径”上必然得到最优解迷宫所有可走格子之间的移动代价都是 1没有斜坡、没有传送门这是一个典型的无权图。BFS 的扩展顺序天然带着“距离层级”第一轮访问起点相邻层第二轮访问距离为 2 的格子。当某个格子第一次被访问时这个访问距离一定是从起点到它的最短距离。反过来看 DFS它会顺着一条路走到黑哪怕这条路绕了一大圈DFS 也不会主动切换到更短的分支除非额外记录全局最短路并多次回溯。BFS 能保证第一次到达终点时路径最短的原因很简单队列按入队顺序出队先入队的永远是当前距离最小的节点。这个性质不依赖图的具体结构只要边权全部为 1 就成立。很多同学学完翁恺老师 C 语言课里的栈和队列后第一次体会到“数据结构真的能解决算法问题”往往就是在这个迷宫项目上。下面进入完整实现。4.2 队列直接用数组模拟比链表版本更省事BFS 需要一个队列C 标准库里没有现成容器。如果只是做题可以用 STL 的queue但纯 C 项目里我更习惯用数组模拟循环队列。这样代码短、无动态内存分配、也不会因为malloc失败导致崩溃。队列元素不需要存完整坐标对象只需要一个能唯一标识格子的编号常见做法是把(row, col)编码成row * cols col的线性索引。int queue[MAX_ROW * MAX_COL]; // 队列数组存放格子编号 int head 0, tail 0; // 队头、队尾下标 int visited[MAX_ROW][MAX_COL] {0}; int prev_row[MAX_ROW][MAX_COL]; // 记录前驱行 int prev_col[MAX_ROW][MAX_COL]; // 记录前驱列 queue[tail] start; visited[start_r][start_c] 1; while (head tail) { int cur queue[head]; int cr cur / maze-cols; int cc cur % maze-cols; if (cr end_r cc end_c) break; for (int i 0; i 4; i) { int nr cr dirs[i][0]; int nc cc dirs[i][1]; if (nr 0 || nr maze-rows || nc 0 || nc maze-cols) continue; if (maze-map[nr][nc] CELL_WALL) continue; if (visited[nr][nc]) continue; visited[nr][nc] 1; prev_row[nr][nc] cr; prev_col[nr][nc] cc; queue[tail] nr * maze-cols nc; } }队列容量MAX_ROW*MAX_COL完全够用每个格子最多入队一次最坏情况下所有格子都入队也填不满整个数组。visited在入队时立即标记而不是在出队时标记这个细节能杜绝同一个格子被重复加入队列。prev_row和prev_col记录的是“从哪个格子走到了当前格子”回溯时的作用等同链表里的next指针翻转。提示检查边界、检查墙、检查访问标记这三个 continue 的顺序不能乱。先判断数组越界再访问map这是避免非法地址读写的关键也是 c 语言内存管理里最基础的一课。4.3 路径回溯站在终点倒着走走出起点BFS 跑完只得到了“终点被访问到了”的结果没有直接给出路径。回溯的原理是从终点开始反复用prev_row/prev_col找到“上一个格子”一直走到起点然后把经过的格子序号压入栈最后依次弹栈输出。栈同样可以用数组模拟或者用一个简单的递归函数打印。递归打印代码更短但迷宫大时栈深度可能到几千层稳妥起见用循环加数组翻转。void printPath(Maze *maze, int prev_row[MAX_ROW][MAX_COL], int prev_col[MAX_ROW][MAX_COL], int end_r, int end_c) { if (!visited[end_r][end_c]) { printf(起点到终点不可达\n); return; } int path[MAX_ROW * MAX_COL][2]; int len 0; int r end_r, c end_c; while (!(r maze-start_row c maze-start_col)) { path[len][0] r; path[len][1] c; len; int tr prev_row[r][c]; int tc prev_col[r][c]; r tr; c tc; } path[len][0] r; path[len][1] c; len; printf(最短路径经过 %d 个格子总步数 %d\n, len, len - 1); for (int i len - 1; i 0; i--) { printf((%d,%d), path[i][0], path[i][1]); if (i 0) printf( - ); } printf(\n); }path数组是从终点到起点的顺序所以输出时倒着遍历正好还原成从起点到终点的路径。len - 1是步数因为格子数比步数多 1。这里有个容易算错的地方如果起点和终点相邻len 为 2步数为 1输出长度 2 的路径逻辑一致。想要更直观的效果可以把路径上的格子改成*字符调用printMaze再渲染一遍这样终端里能看到 BFS 找出的实际路线。4.4 BFS、DFS、Dijkstra 在迷宫场景下的选型对比做迷宫最短路径最容易困惑的是什么时候用 BFS、什么时候用 Dijkstra、什么时候能凑合用 DFS。这三者在迷宫类问题上的核心差异如下算法适用条件能否保证最短典型实现难度DFS只求可行路径、连通性否递归代码短BFS边权全部相等是需要队列代码中等Dijkstra边权不相等如不同地形耗时不同是需要优先队列或邻接表迷宫移动成本恒为 1BFS 就是理论最优解Dijkstra 在这里退化成 BFS 没有任何优势。如果以后做“沙漠迷宫、水路迷宫”这类带权扩展把队列换成最小堆即可。还有一种自适应迷宫算法思路是根据路径搜索过程中的访问密度动态调整搜索方向优先级本质上还是在 BFS 框架上的启发式优化后面章节单独展开。5. 进阶技巧方向优先级剪枝、双向BFS与A*估价5.1 方向数组的排序本身就是一种贪心加速BFS 会遍历所有距离小于终点距离的格子搜索范围在迷宫较大时仍然可观。一个改动成本几乎为零的优化是让方向数组优先朝向终点所在的大致方向。例如终点在起点右下角就把下、右放在上、左前面让 BFS 更早逼近终点。虽然不能减少最坏情况下的复杂度但在多数手工创建的规则迷宫里平均访问格子数能明显下降。实现时把dirs数组重新排列即可BFS 代码完全不用动。5.2 双向BFS从起点和终点同时扩展交汇即最短双向 BFS 是迷宫最短路径里性价比很高的升级思路起点方向和终点方向各维护一个队列、各自维护访问标记每轮交替扩展一层。当某一方扩展到了对方已经访问过的格子说明两条路径相遇把两段路径拼接起来就是完整路径。理论上能把搜索次数降到原来的大约一半迷宫规模越大收益越明显。缺点是代码量几乎翻倍且需要额外记录“每一步是从哪一端扩展的”所以适合作为提交作业里的“进阶加分项”不适合写进 150 行的演示代码里。5.3 用“反向验证”确认路径真的最短写完 BFS 后验证结果比看起来麻烦肉眼数一遍路径长度很容易看错。一个可靠办法是把 BFS 打印出的路径步数len-1和起点终点的曼哈顿距离比较如果两者相等说明这条路径是理论最短路如果步数大于曼哈顿距离则路径里一定有绕路。曼哈顿距离计算很简单abs(end_row - start_row) abs(end_col - start_col)因为它代表了“不走回头路”的下界。拿这个下界跟 BFS 结果做断言可以作为main函数出口处的自检逻辑。另一层验证是输出每格到起点的最短距离矩阵把 4.2 节里的visited换成整数数组同时记录距离值目测距离矩阵数值每个格子是否满足“相邻可走路格差不超过 1”这个性质比单看一条路径更严格。把它打印出来就能直观确认 BFS 的正确性。本文还有配套的精品资源点击获取