简介：这是一份面向数据结构课程设计与C++算法练习者的「老鼠走迷宫」项目资料，适合用来理解二维数组建模、深度优先搜索生成迷宫以及回溯求解路径等核心思路。压缩包共27个文件、约148.59MB，包含C++源码与头文件、Visual Studio解决方案及工程配置、编译产生的中间文件和可执行程序，另附mp4操作与素材视频、说明文本和运行日志，便于读者直接编译运行并对照观察迷宫生成与路径搜索效果。已有1391人学习，说明该项目在课程设计场景中具有一定参考价值。读者可据此梳理从随机迷宫生成、DFS遍历回溯到终点判定的完整实现链路，结合视频与说明排查环境配置和编译运行问题，并在此基础上改造迷宫尺寸、初始条件或路径展示方式，作为课设提交与算法巩固的实践底稿。

1. 老鼠走迷宫不是“递归四行”：课设里真正要交的是可验证的路径

c++ 数据结构课设里，“老鼠走迷宫”几乎是出场率最高的题目之一。很多人第一反应是递归四行代码，把迷宫当二维字符数组，能打印一条路径就交差。但真正让课设翻车的，往往不是“会不会写 DFS”，而是路径穿墙、终点不可达、BFS 写成 DFS 还声称最短。这个资源适合正在做课设、需要可复现实现的人：它把迷宫建模、栈和队列选型、路径回溯、测试校验串成一条线，拿到源码后能先跑通，再按参数和边界用例逐项改。下面按“能运行、能解释、能验收”的顺序拆。

2. 迷宫建模：把二维字符图落成 C++ 的节点、边和方向数组

拿到源码包后，我一般先不看搜索函数，而是看输入约定。课设资源最容易出现的分歧不是算法，而是迷宫到底用0/1还是#/.表示，起点终点是S/E还是坐标输入。数据结构选型上，课设规模通常不大，二维字符网格比邻接表更直观：每个可走格子是一个隐式节点，上下左右四条边由方向数组生成。邻接表适合稀疏大图，但在这个场景里会增加输入解析和调试成本，除非题目明确要求“图结构存储”，否则网格足够。

2.1 用 char 网格还是邻接表：课设规模下的取舍

我见过不少同学一上来就建vector<vector<int>> adj，结果光把字符迷宫转成节点编号就写了半天，后面回溯路径还要反查坐标。老鼠走迷宫的验收点通常是“能不能走通、路径是否合法、最短步数是多少”，不是“邻接表写得多漂亮”。在n*m不超过几万的情况下，vector<string>存网格、vector<vector<int>>存访问状态，内存和速度都够用。真正需要邻接表的场景是格子之间不是四邻接，或者边权不同；普通迷宫课设没必要绕这个弯。

#include <bits/stdc++.h> using namespace std; struct Pos { int r, c; }; // 方向顺序会直接影响 DFS 第一条路径和 BFS 同长度多解的选择 const int dr[4] = {-1, 1, 0, 0}; // 上、下、左、右 const int dc[4] = {0, 0, -1, 1}; struct Maze { int n = 0, m = 0; vector<string> g; Pos start{-1, -1}, goal{-1, -1}; bool inside(int r, int c) const { return r >= 0 && r < n && c >= 0 && c < m; } bool walkable(int r, int c) const { if (!inside(r, c)) return false; return g[r][c] != '#' && g[r][c] != '1'; } }; bool readMaze(const string& path, Maze& maze) { ifstream fin(path); if (!fin) return false; fin >> maze.n >> maze.m; maze.g.assign(maze.n, ""); for (int i = 0; i < maze.n; ++i) { fin >> maze.g[i]; for (int j = 0; j < maze.m; ++j) { if (maze.g[i][j] == 'S') maze.start = {i, j}; if (maze.g[i][j] == 'E') maze.goal = {i, j}; } } return maze.start.r != -1 && maze.goal.r != -1; }

上面这段代码解决三件事：把行列规模读进来、保存字符网格、定位起点和终点。inside先做边界判断，walkable再把墙和越界合并，后面 DFS 和 BFS 都复用这一层，避免每个搜索函数各写一套越界条件。方向数组我固定成“上、下、左、右”，这不是玄学，而是为了让多解输出可复现：同一个迷宫、同一份代码，每次跑出来的第一条路径一致，验收时才好解释。参数上，n和m是行数和列数，g按行存字符串，start和goal用Pos保存；如果输入里没有S/E，读入函数直接返回失败，不要等到搜索阶段才发现起点是(-1,-1)。

2.2 输入约定与方向数组：先把边界条件钉死

输入格式建议在源码说明里写死，不要一边用cin >>一边用getline混读。常见约定是第一行两个整数n m，接下来n行每行m个字符，#或1表示墙，.或0表示通路，S起点，E终点。这个约定和 c++ 数据结构课设里常见的“二维数组表示图”一致，改起来也简单。下面是一份最小输入样例和编译命令，目的是先形成“读入—搜索—输出”的闭环，再谈优化。

# 编译时打开警告，越界和未初始化最容易在这里暴露 g++ -std=c++17 -Wall -Wextra -O2 main.cpp -o maze # 运行：把迷宫文件作为参数传入，避免路径写死在代码里 ./maze maze.txt

编译命令里的-Wall -Wextra不是摆设。课设代码里常见的“变量未初始化”“有符号无符号比较”都会在这里报警，尤其是int和size_t混用导致的边界判断翻车。-O2对课设规模影响不大，但压测随机大迷宫时能减少等待。参数maze.txt是输入文件路径，我一般会让程序支持“不传参数就从标准输入读”，这样在线评测和本地文件都能用。注意不要把输入文件路径写成绝对路径，换一台机器就废了。

注意：先把起点、终点、墙的字符约定固定成一张表，再写搜索。不同源码包可能用0/1，也可能用#/.，适配层只放在读入函数里，不要污染 DFS/BFS。

2.3 编译与运行的最小闭环

在改算法之前，先让程序对一份 5x5 小迷宫输出“起点、终点、是否可达”。这一步看起来笨，但能省掉后面大量“到底是搜索错了还是读入错了”的争论。我的习惯是加一个--dump参数，把读入后的网格和起点终点打印出来，确认坐标没有行列颠倒。参数解析不需要复杂库，argc/argv足够。下面这段不是完整 main，而是验证读入的骨架：先打印n m、起点终点，再决定进 DFS 还是 BFS。

int main(int argc, char** argv) { string input = (argc > 1) ? argv[1] : "maze.txt"; Maze maze; if (!readMaze(input, maze)) { cerr << "read maze failed: " << input << "\n"; return 1; } cout << "n=" << maze.n << " m=" << maze.m << "\n"; cout << "start=(" << maze.start.r << "," << maze.start.c << ") "; cout << "goal=(" << maze.goal.r << "," << maze.goal.c << ")\n"; return 0; }

这段 main 只做读入校验，不承担搜索。argc > 1时用命令行第一个参数作为文件名，否则回退到maze.txt；读入失败返回非零，方便脚本判断。输出里行列分开打印，能快速发现“把x/y和r/c搞混”的问题。等这一步稳定了，再把dfsStack或bfsQueue接进来。很多课设翻车不是算法不会，而是读入阶段已经把起点读错，后面怎么调都是黑匣子。

3. DFS 手写栈：为什么课设演示用栈比递归更稳

DFS 是老鼠走迷宫最直观的做法：从起点出发，按方向顺序尝试，能走就前进，走不通就回退。递归写法短，但递归深度等于路径长度，深迷宫或大面积连通区域可能把调用栈压爆。课设演示场景里，老师不一定给你小数据，随手画一个 100x100 的全通路迷宫，递归深度就可能上万。显式栈把“回退”这件事放到堆内存里，深度可控，也更容易在调试器里观察栈内容。代价是代码多几行，但换来的是可解释性和稳定性。

3.1 递归 DFS 的爆栈边界与显式栈替代

递归 DFS 的核心是“函数调用栈保存现场”，显式栈则自己保存待访问节点。下面这版dfsStack用stack<Pos>存待探索格子，visited在入栈时标记，prev记录每个格子是从哪里来的。注意：DFS 找到的路径不一定最短，它只是“一条可行路径”。如果课设要求最短步数，应该用下一章的 BFS；如果只要求走通并输出路径，DFS 足够。参数上，prev初始化为-2表示未访问，起点prev设为-1表示无前驱，回溯时遇到-1停止。

bool dfsStack(const Maze& maze, vector<vector<int>>& prev) { int n = maze.n, m = maze.m; prev.assign(n, vector<int>(m, -2)); // -2 未访问，-1 起点 stack<Pos> st; st.push(maze.start); prev[maze.start.r][maze.start.c] = -1; while (!st.empty()) { Pos cur = st.top(); st.pop(); if (cur.r == maze.goal.r && cur.c == maze.goal.c) return true; for (int d = 0; d < 4; ++d) { int nr = cur.r + dr[d]; int nc = cur.c + dc[d]; if (!maze.walkable(nr, nc)) continue; if (prev[nr][nc] != -2) continue; // 已入栈或已访问 prev[nr][nc] = cur.r * m + cur.c; // 编码前驱坐标 st.push({nr, nc}); } } return false; }

这段代码的关键在标记时机：prev[nr][nc]在入栈前就写入，避免同一个格子被多个方向重复压栈。如果等到出栈才标记，栈里可能出现大量重复节点，深迷宫下内存和时间都会变差。prev存的是前驱的线性编码r*m+c，回溯时再解码成行列，比存Pos省一点空间，也方便做二维数组索引。参数maze只读，prev是输出参数；返回true表示找到终点，false表示不可达。方向数组顺序决定 DFS 先往哪边走，所以同一迷宫换方向顺序，路径形态会变，但可达性不变。

3.2 用 prev 编码回溯路径

找到终点后，路径还在prev里，需要从终点一路走回起点，再反转输出。下面buildPath负责这件事：如果终点prev还是-2，说明没访问到，直接返回空路径；否则不断解码前驱，直到遇到-1。这里最容易翻车的是“把起点漏掉”或“路径反着打印”。我的习惯是回溯时先把终点压进去，循环条件写成cur != start，最后再补起点，输出前reverse。

vector<Pos> buildPath(const Maze& maze, const vector<vector<int>>& prev) { vector<Pos> path; int m = maze.m; Pos cur = maze.goal; if (prev[cur.r][cur.c] == -2) return path; // 不可达 while (true) { path.push_back(cur); int code = prev[cur.r][cur.c]; if (code == -1) break; // 到起点 cur = {code / m, code % m}; } reverse(path.begin(), path.end()); return path; }

buildPath的输入是迷宫和prev，输出是从起点到终点的坐标序列。code / m和code % m是解码，前提是编码时用r*m+c，行列不要写反。如果终点不可达，prev为-2，函数返回空vector，调用方据此输出“不可达”，不要硬打印一条空路径。路径反转后，第一个元素应该是起点，最后一个元素是终点，这个不变量可以在测试里断言。把路径打印成(r,c)序列或箭头图都行，但建议同时输出步数path.size()-1，方便和 BFS 结果对照。

3.3 方向顺序如何影响第一条路径

DFS 的方向顺序不是无关紧要的装饰。假设迷宫有一条向上绕远的路和一条向右直达的路，方向数组先上后右，DFS 就可能先钻远路。课设验收时如果老师拿同一迷宫对比不同同学的结果，路径不一样很正常，但你要能解释“DFS 只保证可行，不保证最短”。如果题目要求“按字典序最小”或“固定方向优先”，就把方向数组固定成题目要求，并在说明里写清楚。我的做法是把方向顺序提取成常量，不散落在搜索函数里，这样换顺序只改一处，测试也能复现。

提示：DFS 的visited必须在入栈时标记，不要等出栈。显式栈的“后进先出”会让搜索顺序和递归不完全一样，但可达性判断等价。

4. BFS 队列求最短路径：把“能走通”升级成“步数最少”

如果课设要求“最短路径”或“最少步数”，DFS 就不能直接交差。BFS 按层扩展，第一次到达终点时的步数就是最短步数，这是队列先进先出的直接结果。实现上和 DFS 很像，只是容器从stack换成queue，另外用dist记录步数。很多同学把 BFS 写成“队列里塞节点，但标记还是出队才做”，结果同一层重复入队，步数被污染。下面这版把dist初始化为-1，起点为0，入队时立刻更新，避免重复。

4.1 BFS 队列模板与 dist 数组

BFS 的核心是“先入先出、按层扩展”。queue<Pos>存待扩展节点，dist存起点到每个格子的最短步数，prev仍然存前驱编码。起点入队时dist=0，之后每扩展一个可走且未访问的邻居，dist=dist[cur]+1，并把前驱写成当前格子。第一次弹出终点时就可以停，因为队列顺序保证此时步数最小。参数上，dist的-1既表示未访问，也表示不可达；如果终点最终仍是-1，输出不可达。

bool bfsQueue(const Maze& maze, vector<vector<int>>& dist, vector<vector<int>>& prev) { int n = maze.n, m = maze.m; dist.assign(n, vector<int>(m, -1)); prev.assign(n, vector<int>(m, -2)); queue<Pos> q; q.push(maze.start); dist[maze.start.r][maze.start.c] = 0; prev[maze.start.r][maze.start.c] = -1; while (!q.empty()) { Pos cur = q.front(); q.pop(); if (cur.r == maze.goal.r && cur.c == maze.goal.c) return true; for (int d = 0; d < 4; ++d) { int nr = cur.r + dr[d]; int nc = cur.c + dc[d]; if (!maze.walkable(nr, nc)) continue; if (dist[nr][nc] != -1) continue; // 已访问 dist[nr][nc] = dist[cur.r][cur.c] + 1; prev[nr][nc] = cur.r * m + cur.c; q.push({nr, nc}); } } return false; }

bfsQueue返回是否可达，dist和prev都是输出参数。dist的初始值-1很关键：如果初始化为0，你就分不清“起点”和“未访问”。prev的-2与 DFS 版本保持一致，回溯函数可以复用。BFS 的方向顺序会影响同长度路径的选择：例如两条路都是 8 步，先上后右和先右后上输出不同，但步数相同。如果题目要求固定输出，就在说明里写清方向优先级，不要把“多解”当成 bug。

4.2 最短路径回溯与多解输出

BFS 的回溯和 DFS 共用buildPath，因为prev编码规则一样。区别在于dist还可以用来输出“最少步数”。下面这段调用示例先跑 BFS，再取路径，最后打印步数和坐标序列。如果不可达，path为空，直接输出提示。这里不要用path.size()当步数，因为路径点数是步数加一；输出path.size()-1更准确。多解场景下，同一最短步数可能对应多条路径，当前实现只输出按方向顺序走出来的第一条，这通常满足课设要求。

vector<vector<int>> dist, prev; if (bfsQueue(maze, dist, prev)) { vector<Pos> path = buildPath(maze, prev); cout << "shortest steps = " << dist[maze.goal.r][maze.goal.c] << "\n"; cout << "path points = " << path.size() << "\n"; for (auto& p : path) { cout << "(" << p.r << "," << p.c << ") "; } cout << "\n"; } else { cout << "goal unreachable\n"; }

这段调用先判断可达性，再回溯路径。dist[goal]是最短步数，path是坐标序列，两者应当满足dist[goal] == path.size()-1，可以在测试里断言。如果不等，通常是prev被覆盖或dist更新时机错了。多解输出不需要把所有路径都列出来，课设通常只要求一条最短路径；如果题目要求“所有最短路径”，那就要改成记录多前驱或跑第二遍搜索，复杂度会上去，别在一个prev数组上硬塞。当前版本的参数简单：maze只读，dist和prev输出，调用方负责打印。

4.3 和 DFS 的结果对照

同一份迷宫，DFS 和 BFS 的结果经常不一样：DFS 可能 30 步，BFS 可能 18 步，这不是谁写错了，而是搜索策略不同。我的验收习惯是拿 BFS 的dist当基准，检查 DFS 路径是否合法、是否可达，但不要求步数相等。如果 DFS 路径步数小于 BFS，那一定是 BFS 实现有问题，因为 BFS 的最短性由队列顺序保证。对照时重点看三件事：起点终点是否一致、路径是否每步相邻、路径上是否没有墙。把这三项写成断言，比盯着屏幕看箭头图可靠得多。

这张表不是让你背，而是排错时定位：如果题目要最短却交了 DFS，算法选型就错了；如果 BFS 步数不是最小，先查dist是否入队即更新，再查队列是否真的先进先出。参数上，DFS 的prev和 BFS 的prev可以共用回溯函数，但dist只有 BFS 需要。把两种搜索放在同一个Maze结构上跑，输入只读一次，对照测试会轻松很多。

5. 避坑排查：五个让路径“穿墙”或死循环的现场

这一章按“现象 → 原因 → 解决”记五个课设现场。它们不是理论难点，而是验收时最容易被追问的地方。每个问题我都建议先用小迷宫复现，再改代码；不要一上来就调大迷宫，数据越大越难定位。下面五条覆盖边界、标记、递归、回溯和输入，基本能把老鼠走迷宫的主要翻车点串起来。

5.1 路径穿墙：边界判断写反或方向数组越界

现象：输出的路径里出现墙格子，或者坐标跑到-1和n外面。原因通常有两个：inside判断写成r > 0 && r < n，漏掉第 0 行；或者方向数组的dr/dc顺序和坐标含义对不上，把行列当成了x/y。解决方法是把边界判断收口到walkable，所有搜索只调这一个函数，不在每个方向里手写条件。再加一条路径合法性校验：相邻点曼哈顿距离必须为 1，且每个点都可走。这样穿墙问题会在测试阶段暴露，而不是验收时被肉眼抓到。

bool validPath(const Maze& maze, const vector<Pos>& path) { if (path.empty()) return false; if (path.front().r != maze.start.r || path.front().c != maze.start.c) return false; if (path.back().r != maze.goal.r || path.back().c != maze.goal.c) return false; for (size_t i = 1; i < path.size(); ++i) { int d = abs(path[i].r - path[i-1].r) + abs(path[i].c - path[i-1].c); if (d != 1) return false; if (!maze.walkable(path[i].r, path[i].c)) return false; } return true; }

validPath检查三件事：起点对不对、终点对不对、每一步是否相邻且可走。abs的曼哈顿距离判断能抓住“斜着走”和“跳格”的问题，walkable能抓住穿墙。参数path是回溯出来的坐标序列，空路径直接判失败。这个函数不依赖 DFS 或 BFS，两种搜索结果都能校验。把它接在输出前，路径不合法就打印错误并退出，别让一条坏路径混进验收截图。

5.2 死循环与重复入队：visited 标记时机错

现象：程序卡住不结束，或者队列/栈内存一路涨。原因多半是“出队才标记访问”，导致同一格子被多个邻居反复压入；或者prev判断和visited判断混用，已经入队的节点又被当成未访问。解决方法是统一标记时机：DFS 入栈前写prev，BFS 入队前写dist，并且判断条件用同一个数组。不要一边用visited一边用prev != -2，两套状态容易打架。调试时在入队/入栈处打印节点和步数，看同一个坐标是否重复出现，重复就是标记晚了。

5.3 递归 DFS 爆栈：深迷宫下程序直接崩溃

现象：小迷宫正常，换成大面积连通迷宫就异常退出，调试器显示栈溢出。原因是用递归 DFS，递归深度等于搜索路径长度，全通路迷宫可能达到n*m层。解决方法是改成显式stack，把“回退”交给堆上的容器；如果课设必须保留递归，就加深度限制并在说明里写清适用范围。参数上，显式栈版本不需要调递归深度，但要注意stack的内存增长；BFS 的queue在最坏情况下也会存很多节点，压测时看内存占用。

5.4 路径反序与丢起点：回溯循环条件写错

现象：输出从终点开始，或者路径里没有起点。原因通常是回溯时先反转再补起点，或者循环条件写成while (prev[cur] != -1)导致起点没被压入。解决方法是固定顺序：先把终点压入，循环直到cur等于起点，最后再补起点，最后统一reverse。用validPath校验首尾，能直接抓住这个问题。参数上，prev[start] = -1是停止标记，prev的-2是未访问，两个值不要混。

5.5 输入读歪：getline 与 cin 混用导致行列错位

现象：迷宫图整体错一行，或者第一行字符被吃掉。原因是用cin >> n >> m后直接getline，缓冲区里残留换行；或者每行字符串长度不等于m，读入后没有校验。解决方法是统一用fin >> g[i]读字符串，读完后检查g[i].size() == m；如果要读含空格的图，再考虑getline并处理换行。参数上，n/m是行列规模，g每行长度必须一致，起点终点必须存在。读入失败直接返回，不要带着半截数据进搜索。

注意：五个问题里，标记时机和输入错位最容易被忽略。先跑 5x5 小迷宫，再跑 50x50 随机迷宫，最后跑不可达迷宫，三轮下来基本能覆盖。

6. 进阶验证：随机迷宫、路径回放与复杂度对照

课设只交一条路径不够稳，我一般会补一个随机迷宫生成器和一个路径校验器，用固定种子批量跑。生成器不必追求完美迷宫，按概率撒墙、保证起点终点可走即可；校验器用上一章的validPath，再对照 BFS 的dist检查最短性。下面这段用固定种子生成n*m迷宫，墙比例p控制在 0.25 左右，太高会大量不可达，太低迷宫没有区分度。跑 100 组，记录 DFS 可达率、BFS 可达率和路径合法率，比单张截图有说服力。

Maze randomMaze(int n, int m, double p, unsigned seed) { mt19937 rng(seed); uniform_real_distribution<double> prob(0.0, 1.0); Maze maze; maze.n = n; maze.m = m; maze.g.assign(n, string(m, '.')); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (prob(rng) < p) maze.g[i][j] = '#'; maze.start = {0, 0}; maze.goal = {n - 1, m - 1}; maze.g[0][0] = 'S'; maze.g[n - 1][m - 1] = 'E'; return maze; }

randomMaze的参数是行列、墙比例和种子；固定种子保证复现，p越大越容易不可达。生成后强制把起点终点改成可走，避免刚开局就失败。批量测试时，BFS 返回不可达就跳过路径校验，只统计可达率；DFS 和 BFS 的可达结论必须一致，不一致就查标记逻辑。复杂度上，两种搜索都是O(n*m)，额外空间也是O(n*m)；DFS 递归版还有调用栈开销，显式栈和队列则看容器实现。

压测时不要把每个路径点都cout，I/O 会盖过算法耗时；把结果重定向到文件或只输出统计值。我吃过一次亏：本地跑 200x200 觉得慢，最后发现是调试打印没关。从那以后我每次交课设前都强制跑一遍路径合法性校验、不可达用例和固定种子随机迷宫，再提交。源码包拿到手后，先按输入约定跑通最小闭环，再改方向顺序和测试参数，基本不会在验收现场翻车。希望帮到你。

本文还有配套的精品资源，点击获取