尧图网页设计 
经典算法里的迷宫问题表面上是找一条从入口到出口的路实际练习的是栈这种数据结构的回退能力。很多人第一次学数据结构与算法时对数组、链表还能靠直觉理解一到栈就只剩下“后进先出”四个字真到写代码时不知道怎么用。迷宫问题刚好把栈从课本概念拉到了可运行的场景里每走一步压栈走不通就弹栈回到上一个岔路口继续试。它适合刚接触数据结构与算法的同学也适合准备面试、做小游戏寻路、写全栈项目里路径搜索模块的人。栈的应用不是背定义而是把“当前路径”和“还能退回去的选择点”管理清楚。1. 迷宫问题与栈先把回退机制想明白1.1 迷宫问题的真实难点不是找路而是管理选择点迷宫通常用一个二维矩阵表示0 代表通道1 代表墙入口和出口是坐标。人眼扫一遍图很容易看出路径但程序不知道哪条路能通它只能一步一步试探。真正的难点在于走到岔路口时该往哪个方向走走错了怎么回到岔路口回到岔路口之后怎么避免又走进刚才那条死胡同如果只用变量记录当前位置程序走错后就回不去了因为上一个位置已经被覆盖。我们需要一个结构按照“最近一次选择”的顺序保存路线刚走过的位置在顶上更早走过的位置在下面。栈的后进先出特性刚好匹配这个需求。栈顶是当前位置压栈就是前进弹栈就是回退。这个机制在算法里叫回溯而回溯搜索最直接的实现方式之一就是栈。很多人把迷宫问题当成简单的递归练习其实递归本质上也是栈。函数调用时返回地址、局部变量、参数会被压入调用栈函数返回时自动弹栈。写递归版迷宫时觉得代码短是因为系统帮你维护了栈写显式栈版迷宫时代码更长但你能清楚看到每一步栈里有什么。对学习者来说这两条路线都值得写一遍。1.2 后进先出和回溯搜索的对应关系栈的规则是后进先出最后压入的元素最先弹出。放到迷宫问题里搜索过程可以这样描述从入口开始把入口坐标压入栈。查看栈顶位置如果就是出口搜索结束。否则按预先定义的方向顺序尝试相邻格子。如果某个相邻格子是通道且没有走过就标记它并把它压入栈。如果四个方向都走不通说明栈顶位置是死胡同把它弹出栈。弹出后新的栈顶就是上一个岔路口继续尝试它剩下的方向。这里的“尝试剩余方向”是关键。假如栈里只存坐标弹栈回到岔路口后程序不知道哪些方向已经试过可能会重新试同一条死路造成死循环。所以更稳妥的做法是让栈元素保存坐标和“下一步要试的方向编号”。当元素第一次入栈时方向编号为 0之后每次取栈顶都从当前方向编号开始试试过一个方向就把编号加一四个方向都试完还没成功就弹栈。这样做虽然多存了一个整数但逻辑非常清晰。用生活化类比栈就像你走迷宫时手里拿的一根绳子每走到一个新位置就在地上钉一个钉子绳子从入口一路拉过来。走错了你顺着绳子退回上一个钉子而不是凭空瞬移。栈里的元素就是这些钉子栈顶就是绳子末端。1.3 递归、显式栈、队列三条路线怎么选迷宫搜索不只有一种写法。递归版深度优先搜索、显式栈版深度优先搜索、队列版广度优先搜索三者都能找到通路但行为差别很大。方案数据结构找到的路径特点优点风险递归 DFS系统调用栈通常不是最短代码短贴近伪代码迷宫大时递归深度过高可能栈溢出显式栈 DFS自己维护的栈通常不是最短过程可见容量可控需要自己处理方向、标记、弹栈BFS队列在无权迷宫中是最短路径能求最少步数内存占用可能比 DFS 大A* 等启发式优先队列常能更快找到较短路径适合大地图、游戏寻路启发函数设计不好会退化如果你只是想理解栈显式栈 DFS 最适合教学。如果你要交作业或面试递归 DFS 更容易快速写出来。如果你要解决“最少步数出迷宫”别硬用 DFS应该用 BFS。这里没有哪种方案绝对最好只有和场景匹配不匹配。还要提一下 Java 中堆和栈的区别。写 Java 版时会用ArrayDeque当栈栈对象本身在堆里方法调用帧在 Java 虚拟机栈里。递归太深会消耗虚拟机栈抛StackOverflowError而ArrayDeque是堆上的对象只要内存够容量扩展比调用栈灵活。C 语言里如果在函数内声明很大的结构体数组也可能占满线程栈出现栈内存溢出。把大数组放全局或动态分配是常见规避办法。1.4 搜索顺序会让第一条路径完全不同方向数组的顺序会直接影响 DFS 先找到哪条路。比如方向顺序是上、下、左、右程序会优先往上走如果改成左、右、上、下它可能先钻另一条分支。两条路都合法但输出结果不同。很多人调试时发现“我和别人的答案不一样”就怀疑代码错了其实只是搜索顺序不同。我一般建议固定一个方向顺序并在注释里写清楚。比如按上、右、下、左顺时针排列这样手工模拟时也顺。方向顺序本身不影响“能不能找到路”但会影响路径形状、运行时间以及第一次命中出口的快慢。如果迷宫有多个出口搜索顺序还会影响先找到哪个出口。做测试时不要只对比路径字符串最好对比“路径是否连续、是否避开墙、是否从入口到出口”。2. 迷宫数据结构与核心参数设计2.1 地图怎么存二维数组、墙和通道标记最简单的迷宫用二维整数数组int maze[8][8] { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,1,0,1,0,1}, {1,0,0,0,0,1,0,1}, {1,0,1,1,1,1,0,1}, {1,0,1,0,0,0,0,1}, {1,0,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1} };这里 1 是墙0 是通道。外围加一圈 1 可以省掉大量边界判断。否则每次计算nx x dx后都要判断nx 0 nx R代码容易写漏。加一圈墙后只要判断maze[nx][ny] 0越界坐标自然落在墙外不会进入搜索。坐标约定也要统一。常见有两种maze[row][col]或者maze[x][y]。如果写作maze[x][y]那么x表示行y表示列方向数组里dx表示行增量dy表示列增量。如果一会儿把x当列一会儿当行方向就会整体错乱。实际项目里我会把变量命名成row、col少用x、y避免混淆。入口和出口也要明确。比如入口(1,1)出口(6,6)。用坐标表示时要确认地图对应位置确实是 0。曾经见过有人出口写在墙上程序一直找不到排查半天才发现是地图标错。2.2 方向数组顺序、坐标增量和边界判断方向数组是迷宫搜索的核心参数之一。常见写法int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1};这组方向表示上、右、下、左。每次尝试第i个方向时int nx x dx[i]; int ny y dy[i];方向顺序为什么重要因为 DFS 会沿着第一个能走的方向一路深入。如果上方向能走它会先往上如果上方向是死路它会回退再试右。手工模拟时建议把方向数组和编号对应起来方向编号增量含义0(-1, 0)上1(0, 1)右2(1, 0)下3(0, -1)左有些实现会把方向写成 8 个包括斜向。斜向移动的迷宫在游戏里更自然但算法课上通常用 4 方向。如果题目没有明确说明默认 4 方向更稳妥。8 方向会让路径长度定义变化因为斜走一步和直走一步的代价可能不同。2.3 路径栈里到底存什么只存坐标不够栈元素最简单的定义是坐标typedef struct { int row; int col; } Point;但如果只用这个结构弹栈回到岔路口后程序不知道这个位置已经试过哪些方向。它可能会再次尝试同一个方向再次进入同一条死路形成循环。可以在弹栈后重新扫描四个方向用一个 visited 数组判断哪些邻居走过。这样也能工作但每次回到旧位置都要重复扫描效率低逻辑也不够直接。我更推荐保存坐标和方向编号typedef struct { int row; int col; int dir; // 下一个要尝试的方向初始为 0 } StackNode;当节点入栈时dir 0。每次循环取栈顶如果dir 4尝试第dir个方向尝试完后把栈顶的dir加一。如果四个方向都已经试完说明这个位置没有出路弹栈。这个设计让每个格子最多被尝试四个方向且不会重复尝试已经失败的方向。路径栈还需要和访问标记区分开。栈里保存的是“当前正在探索的路径”和“未完成的分支”访问标记保存的是“这个格子已经到过”。找一条路径时格子一旦入栈就标记为已访问弹栈时不取消标记。这样其他分支不会再次进入同一个格子。这样做的代价是只能找到一条路径不能枚举所有路径。如果你要输出所有通路弹栈时必须取消标记并且路径记录方式也要改变。2.4 访问标记的三种策略和取舍访问标记常见有三种做法直接把地图里的 0 改成 2表示已访问。优点是省一个数组缺点是原地图被修改如果想重复使用要恢复。单独开一个visited二维数组初始全 0访问后置 1。优点是地图保持干净缺点是多一份空间。用栈内坐标判断是否已经在路径中。优点是无需额外数组缺点是每次判断都要遍历栈复杂度高。对于 8x8、100x100 这种规模直接改地图或开 visited 数组都行。对于需要反复搜索多个起点的情况单独 visited 更清晰。对于需要输出所有路径的情况标记必须在回溯时撤销否则后续分支会误以为某些格子不能走。有一个容易踩的坑标记的时机。应该在“决定进入某个格子”时标记而不是“从栈里弹出时”标记。如果弹出时才标记同一个格子可能被多个邻居重复压入栈栈迅速膨胀。正确顺序是判断格子可走且未访问立即标记然后压栈。2.5 入口、出口、步数和路径长度的关系路径长度和步数也要定义清楚。如果路径是(1,1) - (1,2) - (2,2)那么经过的格子数是 3移动步数是 2。栈里存的是经过的格子所以“步数 栈大小 - 1”。有些题目要求输出移动次数有些要求输出坐标序列两者不要混。入口和出口如果相同步数为 0。入口如果本身就是墙程序应该立即报错而不是进入搜索。出口如果不可达最后栈会弹空返回失败。实际写代码时建议先做入口和出口的合法性检查再进入主循环。这样排查问题时能快速区分“地图数据错”和“搜索逻辑错”。3. 用显式栈实现深度优先搜索从伪代码到手写代码3.1 核心循环分解压栈、探路、标记、弹栈显式栈版 DFS 的主循环可以拆成四件事压栈从入口开始把入口标记为已访问并压入栈。探路取栈顶如果栈顶就是出口跳出循环否则根据栈顶的dir尝试下一个方向。标记如果相邻格子可走且未访问标记它把新节点压入栈。弹栈如果栈顶四个方向都试完弹出栈顶回到上一层。伪代码如下初始化栈 将入口压栈并标记入口已访问 while 栈不为空: 取栈顶 cur if cur 是出口: 输出栈中路径 结束 if cur.dir 4: 计算下一个方向 nx, ny cur.dir cur.dir 1 if (nx, ny) 可走且未访问: 标记 (nx, ny) 将 (nx, ny, 0) 压栈 else: 弹出栈顶 返回无路径这段伪代码里最容易写错的是cur.dir cur.dir 1的位置。应该在尝试之前加一还是尝试之后加一两种写法只要配套正确都能工作但混用就会导致方向跳号。我习惯在计算完下一个方向后立即加一表示“这个方向已经安排过了”。下次再取栈顶就会从下一个方向继续。还有一个细节如果新节点压栈成功当前循环应该直接进入下一轮而不是继续尝试当前节点的其他方向。DFS 的策略是先深入所以压栈后新的栈顶就是刚进入的格子。这个动作自然由下一轮循环完成。3.2 C 语言版本结构体栈与方向试探下面是一份可以跑的 C 版本核心代码。地图 8x8入口(1,1)出口(6,6)。#include stdio.h #include string.h #define R 8 #define C 8 #define MAX_STACK 1024 int maze[R][C] { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,1,0,1,0,1}, {1,0,0,0,0,1,0,1}, {1,0,1,1,1,1,0,1}, {1,0,1,0,0,0,0,1}, {1,0,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1} }; int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; typedef struct { int row; int col; int dir; } StackNode; StackNode stack[MAX_STACK]; int top -1; int main(void) { int sr 1, sc 1; int er 6, ec 6; maze[sr][sc] 2; stack[top] (StackNode){sr, sc, 0}; while (top 0) { StackNode *cur stack[top]; if (cur-row er cur-col ec) { printf(找到路径步数: %d\n, top); for (int i 0; i top; i) { printf((%d,%d) , stack[i].row, stack[i].col); } printf(\n); return 0; } if (cur-dir 4) { int d cur-dir; cur-dir cur-dir 1; int nr cur-row dx[d]; int nc cur-col dy[d]; if (maze[nr][nc] 0) { maze[nr][nc] 2; stack[top] (StackNode){nr, nc, 0}; } } else { top--; } } printf(没有找到路径\n); return 0; }这份代码里maze是全局数组不占函数栈空间。stack也是全局容量 1024对于 8x8 绰绰有余。如果迷宫很大应该根据行列数动态分配或者至少把MAX_STACK设为R * C。C 语言里如果把这些大数组写在main内部某些环境可能因为线程栈不够而崩溃。这不是算法问题是内存布局问题但调试时很容易误判。3.3 Python 版本列表当栈快速验证思路Python 写迷宫搜索非常快列表append和pop就是天然栈。下面代码用同样的地图和方向。R, C 8, 8 maze [ [1,1,1,1,1,1,1,1], [1,0,0,1,0,0,0,1], [1,1,0,1,0,1,0,1], [1,0,0,0,0,1,0,1], [1,0,1,1,1,1,0,1], [1,0,1,0,0,0,0,1], [1,0,0,0,1,1,0,1], [1,1,1,1,1,1,1,1], ] dirs [(-1, 0), (0, 1), (1, 0), (0, -1)] sr, sc 1, 1 er, ec 6, 6 maze[sr][sc] 2 stack [[sr, sc, 0]] # row, col, next_dir while stack: cur stack[-1] r, c, d cur if r er and c ec: print(找到路径步数:, len(stack) - 1) print([(node[0], node[1]) for node in stack]) break if d 4: cur[2] d 1 nr r dirs[d][0] nc c dirs[d][1] if maze[nr][nc] 0: maze[nr][nc] 2 stack.append([nr, nc, 0]) else: stack.pop() else: print(没有找到路径)Python 版有个小细节stack[-1]取到的是列表对象cur[2] d 1会直接修改栈顶。这个行为和 C 版本的指针操作类似。不要写成r, c, d stack[-1]后只修改局部变量d那样栈里的方向不会更新会导致重复尝试同一个方向。Python 的整数不可变列表元素可变这一点要分清。3.4 Java 版本用 ArrayDeque 而不是老 Stack 类Java 里可以用ArrayDeque当栈。Stack类虽然名字直接但它继承自Vector方法加了同步性能一般新代码里不推荐。import java.util.ArrayDeque; import java.util.Deque; public class MazeStack { static int[][] maze { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,1,0,1,0,1}, {1,0,0,0,0,1,0,1}, {1,0,1,1,1,1,0,1}, {1,0,1,0,0,0,0,1}, {1,0,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1} }; static int[] dr {-1, 0, 1, 0}; static int[] dc {0, 1, 0, -1}; static class Node { int row, col, dir; Node(int row, int col, int dir) { this.row row; this.col col; this.dir dir; } } public static void main(String[] args) { int sr 1, sc 1, er 6, ec 6; DequeNode stack new ArrayDeque(); maze[sr][sc] 2; stack.push(new Node(sr, sc, 0)); while (!stack.isEmpty()) { Node cur stack.peek(); if (cur.row er cur.col ec) { System.out.println(找到路径步数: (stack.size() - 1)); for (Node node : stack) { System.out.print(( node.row , node.col ) ); } return; } if (cur.dir 4) { int d cur.dir; cur.dir; int nr cur.row dr[d]; int nc cur.col dc[d]; if (maze[nr][nc] 0) { maze[nr][nc] 2; stack.push(new Node(nr, nc, 0)); } } else { stack.pop(); } } System.out.println(没有找到路径); } }这里ArrayDeque的push等价于addFirstpop等价于removeFirstpeek看栈顶。遍历Deque时顺序是从队头到队尾也就是从栈顶到栈底打印路径时会反过来。如果要按入口到出口顺序打印可以先用另一个栈转一下或者用LinkedList并手动控制。小细节不影响搜索但输出格式要求严格时要注意。3.5 输出路径栈里保存的到底是什么顺序用上面的写法栈底是入口栈顶是当前位置所以从下标 0 到top遍历就是入口到出口的顺序。C 和 Python 版本都能直接打印。Java 的ArrayDeque迭代顺序是从头到尾而push把新元素放在头部所以迭代顺序是出口到入口。要得到入口到出口可以用ArrayDeque的descendingIterator()或者把节点弹到临时列表再反转或者一开始就用addLast、removeLast模拟栈让迭代顺序符合习惯。路径输出还涉及“路径是否包含入口和出口”。一般包含。步数等于坐标数减一。有些题目要求输出方向序列比如“上右下左”那就需要额外记录每次移动的方向。可以在节点里加一个fromDir字段表示“从哪个方向移动到当前格子”打印时根据fromDir反向查字符。3.6 时间复杂度和空间复杂度怎么算在“只找一条路径”且每个格子最多入栈一次的前提下每个格子最多被检查四个方向所以时间复杂度是 O(R × C)其中 R 是行数C 是列数。空间复杂度也是 O(R × C)因为栈最坏情况下可能保存接近所有格子的路径visited 或地图标记也需要 O(R × C) 的空间。如果题目要求输出所有路径复杂度会变成指数级。因为每个岔路口都可能产生多个分支搜索树可能非常庞大。这种场景下显式栈仍然能用但必须允许弹栈时取消访问标记并且要限制搜索深度或路径数量否则很容易跑不完。场景时间复杂度空间复杂度说明找一条路径 DFSO(R×C)O(R×C)每个格子最多访问一次找所有路径指数级O(R×C)需要回溯撤销标记BFS 最短路O(R×C)O(R×C)队列可能同时保存大量节点A* 启发式取决于启发函数O(R×C)最坏仍可能退化为广搜复杂度分析不是写给别人看的装饰它能帮你判断程序为什么慢。如果 100×100 的迷宫跑了几秒还没结果通常是遇到了重复访问、方向没有推进、或者错误地枚举了所有路径。4. 8x8 迷宫实操栈变化与死胡同回退4.1 准备地图和坐标约定还是用上面那张 8x8 地图。入口(1,1)出口(6,6)。坐标(row, col)方向顺序上、右、下、左。起点入栈后标记为 2。栈初始状态栈底 - 栈顶 (1,1,dir0)此时dir0表示下一步尝试上方向。上方向是(0,1)地图值是 1是墙不能走。于是(1,1)的dir变成 1尝试右方向(1,2)地图值是 0可以走。4.2 手工模拟前几步栈如何增长第一步进入(1,2)(1,1,dir1) - (1,2,dir0)在(1,2)上方向(0,2)是墙右方向(1,3)是墙下方向(2,2)是 0进入(2,2)(1,1,dir1) - (1,2,dir2) - (2,2,dir0)在(2,2)上方向(1,2)已访问右方向(2,3)是墙下方向(3,2)是 0进入(3,2)(1,1,dir1) - (1,2,dir2) - (2,2,dir2) - (3,2,dir0)在(3,2)上方向已访问右方向(3,3)是 0进入(3,3)然后(3,4)再尝试上方向(2,4)进入(2,4)再到(1,4)、(1,5)、(1,6)、(2,6)、(3,6)、(4,6)、(5,6)、(6,6)。这条路线会成功。但 DFS 不一定一开始就沿着这条成功路线走。如果某个岔路口先选择了死胡同就会看到弹栈。4.3 死胡同回退的现场记录假设在(3,2)时程序先尝试下方向(4,2)。地图(4,2)是 0进入(1,1) - (1,2) - (2,2) - (3,2) - (4,2)在(4,2)上方向已访问右方向(4,3)是 1下方向(5,2)是 1左方向(4,1)是 0于是进入(4,1)... - (3,2) - (4,2) - (4,1)在(4,1)上方向(3,1)是 0但可能已被访问或未访问右方向(4,2)已访问下方向(5,1)是 0进入(5,1)再到(6,1)、(6,2)、(6,3)、(5,3)、(5,4)、(5,5)、(5,6)、(6,6)。这条路也能成功只是不同。为了看到死胡同弹栈我们可以换一个更明确的局部结构某个格子三面是墙只有来路可走。走到那里后四个方向都不可用栈顶被弹出。假设当前栈是(1,1,dir1) - (1,2,dir2) - (2,2,dir2) - (3,2,dir3) - (3,1,dir0)在(3,1)上方向(2,1)是 1右方向(3,2)已访问下方向(4,1)是 0如果下方向也走不通或者已经探索过那么(3,1)的dir会加到 4随后执行pop。弹出后栈顶变回(3,2)它的dir已经在入栈后继续推进于是尝试下一个方向。这个过程就是回溯。操作栈顶变化说明初始(1,1)入口入栈前进(1,2)右方向可走前进(2,2)下方向可走前进(3,2)下方向可走前进(3,1)左方向可走无路弹出 (3,1)四个方向试完回到岔路栈顶变 (3,2)继续尝试剩余方向4.4 最终路径与输出格式当栈顶坐标等于出口(6,6)时遍历栈即可得到路径。按上面的方向顺序和地图可能得到一条路径(1,1) (1,2) (2,2) (3,2) (3,3) (3,4) (2,4) (1,4) (1,5) (1,6) (2,6) (3,6) (4,6) (5,6) (6,6)步数是 14。路径中每一步都是相邻的上下左右移动且没有经过墙。如果你输出的路径不连续通常是坐标记录顺序错了比如 Java 的ArrayDeque迭代顺序反了。如果路径穿墙通常是地图判断条件写错比如把maze[nr][nc] 0写成了! 1而地图里还有标记 2导致已访问格子被当成通道。输出时可以加上方向字符。比如从(1,1)到(1,2)是右打印R从(3,4)到(2,4)是上打印U。方向和坐标一起输出调试时更直观。5. 常见问题与排查技巧5.1 死循环忘了标记或标记太晚迷宫搜索最常见的 bug 是死循环。程序在几个格子之间来回走栈越来越大最后内存耗尽。原因通常是标记时机不对进入新格子时没有标记导致它被不同邻居反复压栈。弹栈时错误地取消了标记但搜索策略又是“找一条路径”导致其他分支重新进入。方向编号没有推进每次取栈顶都从同一个方向开始压入同一个邻居。排查方法很简单在每次压栈和弹栈时打印push (r,c) dir...和pop (r,c) dir...。如果看到同一个坐标被反复 push基本就是标记或方向问题。小地图上手工跑一遍比盯着代码空想快得多。5.2 栈溢出递归深度、显式栈容量和内存区域“栈溢出”在迷宫问题里可能指三种情况递归版递归太深调用栈不够抛出栈溢出错误。显式栈数组开得太小压入时越界。大数组声明在函数栈上占满线程栈。递归版最危险因为迷宫中可能存在一条很长的蛇形路径递归深度等于路径长度。1000×1000 的迷宫如果路径很长递归深度可能上万。C、Java、Python 的默认递归深度限制不同Python 默认大约 1000 层很容易触发RecursionError。解决办法是改用显式栈或者手动调大递归限制但后者不治本。显式栈版要注意容量。最坏情况下栈大小可能达到R × C所以容量至少开到R * C 1。C 语言里用malloc动态分配或者把栈数组设为全局Java 用ArrayDeque会自动扩容Python 列表也会自动扩容。Java 中还要区分堆和栈new Node()对象在堆上ArrayDeque也在堆上方法调用帧在虚拟机栈上。堆内存不足会抛OutOfMemoryError虚拟机栈不足会抛StackOverflowError两者排查方向不同。5.3 找到的路径不是最短DFS 本来就不保证很多人第一次用栈跑完迷宫发现路径绕了一大圈就怀疑代码有 bug。其实 DFS 只保证“找到一条路”不保证“最短”。它的策略是沿一个方向深入到底撞墙再回退。迷宫如果有环DFS 可能先钻一条很长的分支最后才找到出口。要最短路径应该用 BFS。BFS 按层扩展第一次到达出口时经过的步数一定最少。BFS 用队列不用栈。队列是先进先出先进入的节点先扩展所以它能一圈一圈地向外搜索。A* 则是在 BFS 基础上加入启发函数适合大地图游戏寻路。栈适合做回溯、表达式求值、括号匹配、函数调用模拟求最短路时不要硬套。5.4 路径丢失弹栈时把有效路径也删了显式栈保存的是当前搜索路径。如果弹栈逻辑写错比如找到出口后继续弹栈或者弹栈后没有回到正确岔路口路径就可能丢失。常见原因是把“当前节点”和“栈顶节点”混用。在循环中如果先pop再检查出口肯定找不到。正确顺序是先看栈顶判断是否出口再决定尝试方向或弹栈。另一个坑是路径记录和搜索栈分开维护。有些人用一个path列表记录路径又用一个stack做搜索但两者没有同步。弹栈时只弹了stack没弹path最后path里会混入死胡同。要么让搜索栈直接保存路径要么严格同步两个结构。5.5 常见问题速查表现象可能原因解决思路程序死循环未标记访问方向编号未推进入栈时标记尝试后dir压栈越界栈容量小于 R×C容量开到 R×C1 或动态扩容递归报错递归深度过大改用显式栈或限制地图规模路径穿墙可走判断写错只允许maze[nr][nc] 0路径不连续输出顺序反了或路径混入死胡同检查栈迭代顺序和弹栈同步找不到出口出口在墙上、入口标记错、方向数组错打印入口出口值手工走两步路径不是最短用了 DFS改 BFS 或 A*Java 输出反向ArrayDeque 迭代顺序是栈顶到栈底用 descendingIterator 或临时栈5.6 我踩过的几个坑第一个坑是方向数组写成了{0,1},{1,0},{0,-1},{-1,0}以为是上右下左实际是右、下、左、上。代码能跑路径也合法但和手工模拟对不上查了很久才发现顺序问题。后来我固定用注释标清楚每个方向编号省了很多事。第二个坑是在弹栈时取消了地图上的访问标记。当时想“既然回退了这个格子以后也许还能从别的路走”结果程序在环里绕不出来。找一条路径时访问标记表示“这个格子已经确认探索过”不需要取消。只有枚举所有路径时才需要恢复现场。两种目标对应两种标记策略不能混。第三个坑是 C 语言里把StackNode stack[1000000]写在main函数里编译没问题运行直接崩溃。后来改成全局数组或malloc就好了。这个坑和算法无关但新手很容易遇到尤其是从 Python 转 C 的时候。6. 进阶优化与工程化扩展6.1 剪枝和方向启发让 DFS 少走冤枉路DFS 在迷宫里的效率通常够用但如果地图很大、死胡同很多可以通过剪枝减少无效分支。剪枝算法的核心思想是在进入某个格子之前先用简单规则判断它是否可能通向出口。比如如果某个通道格子的上下左右都被墙或已访问格子包围它不可能继续前进可以提前跳过。如果某个区域与出口不连通可以先做连通性标记只搜索连通区域。按曼哈顿距离给方向排序优先尝试离出口更近的方向。曼哈顿距离是abs(row - er) abs(col - ec)。在尝试四个方向时可以先把可走方向按距离从小到大排序再依次入栈。这样 DFS 会更早靠近出口但不保证最短。这个方法在游戏寻路里很常见配合 A* 效果更好。剪枝不会改变算法的正确性前提是剪枝规则不能误删可行路径。比如“某格子四面被墙包围”这种判断是安全的“某格子看起来离出口远”不能直接删只能调整顺序。工程里宁可少剪一点也不要为了速度引入错误。6.2 栈、队列、优先队列分别对应什么算法数据结构搜索策略适合问题栈深度优先搜索回溯、连通性、找一条路径队列广度优先搜索无权图最短路、最少步数优先队列A*、Dijkstra带权图、启发式寻路递归调用栈深度优先搜索代码简洁的回溯栈和队列经常被放在一起讲因为它们的区别就是进出顺序。栈是后进先出队列是先进先出。迷宫问题里把栈换成队列搜索行为就从“一条路走到黑”变成“一圈一圈往外扩”。如果你把代码里的pop改成popleft再把压栈改成入队很可能就得到了 BFS 版本。但要注意BFS 找到出口时不能立即返回吗可以因为 BFS 按层扩展第一次到达出口就是最短路径。6.3 多入口、多出口和动态迷宫怎么处理多入口迷宫的思路是把所有入口先压入栈并标记为已访问。然后正常搜索找到任意出口就结束。如果要求“从最近入口到最近出口”那就不能用普通 DFS应该用多源 BFS所有入口同时入队第一次碰到出口时就是最少步数。多出口也类似。如果只要求找到一个出口正常搜索即可如果要求最近出口用 BFS 或 A*。动态迷宫指搜索过程中障碍会变化比如游戏里的门会开关。这种场景需要把“时间”或“状态”加入节点同一个坐标在不同时间可能是不同状态。搜索空间会变大通常要用带状态的 BFS 或 A*。工程化时建议把地图表示、方向定义、搜索算法分开。地图模块只负责判断某个坐标是否可走搜索模块只负责压栈、弹栈、访问标记输出模块只负责把路径转成坐标序列或方向字符串。这样换地图、换算法、换输出格式时不会互相牵连。6.4 用日志和可视化把栈的变化看清楚学习栈应用时最有效的方法不是盯着代码而是把栈的变化打印出来。可以在每次循环开头打印step12 top(3,2,dir2) stack_size4 try dir2 - (4,2) push (4,2,dir0)也可以把已访问格子标记为.当前路径标记为*出口标记为E每走一步打印一次地图。小地图上肉眼就能看出程序有没有走错。对于 8x8 迷宫打印 20 步左右就能定位大部分逻辑错误。可视化不一定要做图形界面。终端字符输出就够用。关键是让“栈顶、方向、访问标记、当前路径”四个信息同时可见。很多 bug 之所以难查是因为只能看到最终结果看不到中间状态。把中间状态暴露出来问题往往自己就浮出来了。6.5 从课堂作业到小项目还能怎么扩展迷宫问题可以做得很小也可以继续扩展。比如加一个随机迷宫生成器用深度优先搜索挖通道加一个路径动画用字符逐帧播放加一个关卡编辑器让用户手动改地图或者把搜索算法封装成库在游戏项目里复用。全栈项目里如果需要做简单的寻路演示后端返回迷宫矩阵前端用 Canvas 画格子和路径栈搜索过程可以作为每一步的动画数据返回。如果想让程序更稳可以写几个小测试入口在出口旁边期望步数为 1出口不可达期望返回失败入口是墙期望报错只有一个格子的迷宫期望步数为 0。测试不需要复杂框架一个主函数里多跑几个用例就行。我自己的习惯是先用小地图验证逻辑再用大地图测性能和内存。小地图上手工能算出的结果是最可靠的断言。最后再分享一个实际带新人时的做法不要一上来就写完整代码先让他在纸上画一个 5x5 迷宫然后每一步写出栈里有什么、栈顶方向编号是多少。能手工把死胡同回退画明白的人写代码时基本不会犯方向不推进、标记时机错误这类问题。栈的应用说到底不是语法而是你对“路径”和“回退”这两个动作的理解。 用栈与回溯解决迷宫问题：从后进先出到DFS路径搜索
经典算法里的迷宫问题表面上是找一条从入口到出口的路实际练习的是栈这种数据结构的回退能力。很多人第一次学数据结构与算法时对数组、链表还能靠直觉理解一到栈就只剩下“后进先出”四个字真到写代码时不知道怎么用。迷宫问题刚好把栈从课本概念拉到了可运行的场景里每走一步压栈走不通就弹栈回到上一个岔路口继续试。它适合刚接触数据结构与算法的同学也适合准备面试、做小游戏寻路、写全栈项目里路径搜索模块的人。栈的应用不是背定义而是把“当前路径”和“还能退回去的选择点”管理清楚。1. 迷宫问题与栈先把回退机制想明白1.1 迷宫问题的真实难点不是找路而是管理选择点迷宫通常用一个二维矩阵表示0 代表通道1 代表墙入口和出口是坐标。人眼扫一遍图很容易看出路径但程序不知道哪条路能通它只能一步一步试探。真正的难点在于走到岔路口时该往哪个方向走走错了怎么回到岔路口回到岔路口之后怎么避免又走进刚才那条死胡同如果只用变量记录当前位置程序走错后就回不去了因为上一个位置已经被覆盖。我们需要一个结构按照“最近一次选择”的顺序保存路线刚走过的位置在顶上更早走过的位置在下面。栈的后进先出特性刚好匹配这个需求。栈顶是当前位置压栈就是前进弹栈就是回退。这个机制在算法里叫回溯而回溯搜索最直接的实现方式之一就是栈。很多人把迷宫问题当成简单的递归练习其实递归本质上也是栈。函数调用时返回地址、局部变量、参数会被压入调用栈函数返回时自动弹栈。写递归版迷宫时觉得代码短是因为系统帮你维护了栈写显式栈版迷宫时代码更长但你能清楚看到每一步栈里有什么。对学习者来说这两条路线都值得写一遍。1.2 后进先出和回溯搜索的对应关系栈的规则是后进先出最后压入的元素最先弹出。放到迷宫问题里搜索过程可以这样描述从入口开始把入口坐标压入栈。查看栈顶位置如果就是出口搜索结束。否则按预先定义的方向顺序尝试相邻格子。如果某个相邻格子是通道且没有走过就标记它并把它压入栈。如果四个方向都走不通说明栈顶位置是死胡同把它弹出栈。弹出后新的栈顶就是上一个岔路口继续尝试它剩下的方向。这里的“尝试剩余方向”是关键。假如栈里只存坐标弹栈回到岔路口后程序不知道哪些方向已经试过可能会重新试同一条死路造成死循环。所以更稳妥的做法是让栈元素保存坐标和“下一步要试的方向编号”。当元素第一次入栈时方向编号为 0之后每次取栈顶都从当前方向编号开始试试过一个方向就把编号加一四个方向都试完还没成功就弹栈。这样做虽然多存了一个整数但逻辑非常清晰。用生活化类比栈就像你走迷宫时手里拿的一根绳子每走到一个新位置就在地上钉一个钉子绳子从入口一路拉过来。走错了你顺着绳子退回上一个钉子而不是凭空瞬移。栈里的元素就是这些钉子栈顶就是绳子末端。1.3 递归、显式栈、队列三条路线怎么选迷宫搜索不只有一种写法。递归版深度优先搜索、显式栈版深度优先搜索、队列版广度优先搜索三者都能找到通路但行为差别很大。方案数据结构找到的路径特点优点风险递归 DFS系统调用栈通常不是最短代码短贴近伪代码迷宫大时递归深度过高可能栈溢出显式栈 DFS自己维护的栈通常不是最短过程可见容量可控需要自己处理方向、标记、弹栈BFS队列在无权迷宫中是最短路径能求最少步数内存占用可能比 DFS 大A* 等启发式优先队列常能更快找到较短路径适合大地图、游戏寻路启发函数设计不好会退化如果你只是想理解栈显式栈 DFS 最适合教学。如果你要交作业或面试递归 DFS 更容易快速写出来。如果你要解决“最少步数出迷宫”别硬用 DFS应该用 BFS。这里没有哪种方案绝对最好只有和场景匹配不匹配。还要提一下 Java 中堆和栈的区别。写 Java 版时会用ArrayDeque当栈栈对象本身在堆里方法调用帧在 Java 虚拟机栈里。递归太深会消耗虚拟机栈抛StackOverflowError而ArrayDeque是堆上的对象只要内存够容量扩展比调用栈灵活。C 语言里如果在函数内声明很大的结构体数组也可能占满线程栈出现栈内存溢出。把大数组放全局或动态分配是常见规避办法。1.4 搜索顺序会让第一条路径完全不同方向数组的顺序会直接影响 DFS 先找到哪条路。比如方向顺序是上、下、左、右程序会优先往上走如果改成左、右、上、下它可能先钻另一条分支。两条路都合法但输出结果不同。很多人调试时发现“我和别人的答案不一样”就怀疑代码错了其实只是搜索顺序不同。我一般建议固定一个方向顺序并在注释里写清楚。比如按上、右、下、左顺时针排列这样手工模拟时也顺。方向顺序本身不影响“能不能找到路”但会影响路径形状、运行时间以及第一次命中出口的快慢。如果迷宫有多个出口搜索顺序还会影响先找到哪个出口。做测试时不要只对比路径字符串最好对比“路径是否连续、是否避开墙、是否从入口到出口”。2. 迷宫数据结构与核心参数设计2.1 地图怎么存二维数组、墙和通道标记最简单的迷宫用二维整数数组int maze[8][8] { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,1,0,1,0,1}, {1,0,0,0,0,1,0,1}, {1,0,1,1,1,1,0,1}, {1,0,1,0,0,0,0,1}, {1,0,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1} };这里 1 是墙0 是通道。外围加一圈 1 可以省掉大量边界判断。否则每次计算nx x dx后都要判断nx 0 nx R代码容易写漏。加一圈墙后只要判断maze[nx][ny] 0越界坐标自然落在墙外不会进入搜索。坐标约定也要统一。常见有两种maze[row][col]或者maze[x][y]。如果写作maze[x][y]那么x表示行y表示列方向数组里dx表示行增量dy表示列增量。如果一会儿把x当列一会儿当行方向就会整体错乱。实际项目里我会把变量命名成row、col少用x、y避免混淆。入口和出口也要明确。比如入口(1,1)出口(6,6)。用坐标表示时要确认地图对应位置确实是 0。曾经见过有人出口写在墙上程序一直找不到排查半天才发现是地图标错。2.2 方向数组顺序、坐标增量和边界判断方向数组是迷宫搜索的核心参数之一。常见写法int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1};这组方向表示上、右、下、左。每次尝试第i个方向时int nx x dx[i]; int ny y dy[i];方向顺序为什么重要因为 DFS 会沿着第一个能走的方向一路深入。如果上方向能走它会先往上如果上方向是死路它会回退再试右。手工模拟时建议把方向数组和编号对应起来方向编号增量含义0(-1, 0)上1(0, 1)右2(1, 0)下3(0, -1)左有些实现会把方向写成 8 个包括斜向。斜向移动的迷宫在游戏里更自然但算法课上通常用 4 方向。如果题目没有明确说明默认 4 方向更稳妥。8 方向会让路径长度定义变化因为斜走一步和直走一步的代价可能不同。2.3 路径栈里到底存什么只存坐标不够栈元素最简单的定义是坐标typedef struct { int row; int col; } Point;但如果只用这个结构弹栈回到岔路口后程序不知道这个位置已经试过哪些方向。它可能会再次尝试同一个方向再次进入同一条死路形成循环。可以在弹栈后重新扫描四个方向用一个 visited 数组判断哪些邻居走过。这样也能工作但每次回到旧位置都要重复扫描效率低逻辑也不够直接。我更推荐保存坐标和方向编号typedef struct { int row; int col; int dir; // 下一个要尝试的方向初始为 0 } StackNode;当节点入栈时dir 0。每次循环取栈顶如果dir 4尝试第dir个方向尝试完后把栈顶的dir加一。如果四个方向都已经试完说明这个位置没有出路弹栈。这个设计让每个格子最多被尝试四个方向且不会重复尝试已经失败的方向。路径栈还需要和访问标记区分开。栈里保存的是“当前正在探索的路径”和“未完成的分支”访问标记保存的是“这个格子已经到过”。找一条路径时格子一旦入栈就标记为已访问弹栈时不取消标记。这样其他分支不会再次进入同一个格子。这样做的代价是只能找到一条路径不能枚举所有路径。如果你要输出所有通路弹栈时必须取消标记并且路径记录方式也要改变。2.4 访问标记的三种策略和取舍访问标记常见有三种做法直接把地图里的 0 改成 2表示已访问。优点是省一个数组缺点是原地图被修改如果想重复使用要恢复。单独开一个visited二维数组初始全 0访问后置 1。优点是地图保持干净缺点是多一份空间。用栈内坐标判断是否已经在路径中。优点是无需额外数组缺点是每次判断都要遍历栈复杂度高。对于 8x8、100x100 这种规模直接改地图或开 visited 数组都行。对于需要反复搜索多个起点的情况单独 visited 更清晰。对于需要输出所有路径的情况标记必须在回溯时撤销否则后续分支会误以为某些格子不能走。有一个容易踩的坑标记的时机。应该在“决定进入某个格子”时标记而不是“从栈里弹出时”标记。如果弹出时才标记同一个格子可能被多个邻居重复压入栈栈迅速膨胀。正确顺序是判断格子可走且未访问立即标记然后压栈。2.5 入口、出口、步数和路径长度的关系路径长度和步数也要定义清楚。如果路径是(1,1) - (1,2) - (2,2)那么经过的格子数是 3移动步数是 2。栈里存的是经过的格子所以“步数 栈大小 - 1”。有些题目要求输出移动次数有些要求输出坐标序列两者不要混。入口和出口如果相同步数为 0。入口如果本身就是墙程序应该立即报错而不是进入搜索。出口如果不可达最后栈会弹空返回失败。实际写代码时建议先做入口和出口的合法性检查再进入主循环。这样排查问题时能快速区分“地图数据错”和“搜索逻辑错”。3. 用显式栈实现深度优先搜索从伪代码到手写代码3.1 核心循环分解压栈、探路、标记、弹栈显式栈版 DFS 的主循环可以拆成四件事压栈从入口开始把入口标记为已访问并压入栈。探路取栈顶如果栈顶就是出口跳出循环否则根据栈顶的dir尝试下一个方向。标记如果相邻格子可走且未访问标记它把新节点压入栈。弹栈如果栈顶四个方向都试完弹出栈顶回到上一层。伪代码如下初始化栈 将入口压栈并标记入口已访问 while 栈不为空: 取栈顶 cur if cur 是出口: 输出栈中路径 结束 if cur.dir 4: 计算下一个方向 nx, ny cur.dir cur.dir 1 if (nx, ny) 可走且未访问: 标记 (nx, ny) 将 (nx, ny, 0) 压栈 else: 弹出栈顶 返回无路径这段伪代码里最容易写错的是cur.dir cur.dir 1的位置。应该在尝试之前加一还是尝试之后加一两种写法只要配套正确都能工作但混用就会导致方向跳号。我习惯在计算完下一个方向后立即加一表示“这个方向已经安排过了”。下次再取栈顶就会从下一个方向继续。还有一个细节如果新节点压栈成功当前循环应该直接进入下一轮而不是继续尝试当前节点的其他方向。DFS 的策略是先深入所以压栈后新的栈顶就是刚进入的格子。这个动作自然由下一轮循环完成。3.2 C 语言版本结构体栈与方向试探下面是一份可以跑的 C 版本核心代码。地图 8x8入口(1,1)出口(6,6)。#include stdio.h #include string.h #define R 8 #define C 8 #define MAX_STACK 1024 int maze[R][C] { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,1,0,1,0,1}, {1,0,0,0,0,1,0,1}, {1,0,1,1,1,1,0,1}, {1,0,1,0,0,0,0,1}, {1,0,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1} }; int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; typedef struct { int row; int col; int dir; } StackNode; StackNode stack[MAX_STACK]; int top -1; int main(void) { int sr 1, sc 1; int er 6, ec 6; maze[sr][sc] 2; stack[top] (StackNode){sr, sc, 0}; while (top 0) { StackNode *cur stack[top]; if (cur-row er cur-col ec) { printf(找到路径步数: %d\n, top); for (int i 0; i top; i) { printf((%d,%d) , stack[i].row, stack[i].col); } printf(\n); return 0; } if (cur-dir 4) { int d cur-dir; cur-dir cur-dir 1; int nr cur-row dx[d]; int nc cur-col dy[d]; if (maze[nr][nc] 0) { maze[nr][nc] 2; stack[top] (StackNode){nr, nc, 0}; } } else { top--; } } printf(没有找到路径\n); return 0; }这份代码里maze是全局数组不占函数栈空间。stack也是全局容量 1024对于 8x8 绰绰有余。如果迷宫很大应该根据行列数动态分配或者至少把MAX_STACK设为R * C。C 语言里如果把这些大数组写在main内部某些环境可能因为线程栈不够而崩溃。这不是算法问题是内存布局问题但调试时很容易误判。3.3 Python 版本列表当栈快速验证思路Python 写迷宫搜索非常快列表append和pop就是天然栈。下面代码用同样的地图和方向。R, C 8, 8 maze [ [1,1,1,1,1,1,1,1], [1,0,0,1,0,0,0,1], [1,1,0,1,0,1,0,1], [1,0,0,0,0,1,0,1], [1,0,1,1,1,1,0,1], [1,0,1,0,0,0,0,1], [1,0,0,0,1,1,0,1], [1,1,1,1,1,1,1,1], ] dirs [(-1, 0), (0, 1), (1, 0), (0, -1)] sr, sc 1, 1 er, ec 6, 6 maze[sr][sc] 2 stack [[sr, sc, 0]] # row, col, next_dir while stack: cur stack[-1] r, c, d cur if r er and c ec: print(找到路径步数:, len(stack) - 1) print([(node[0], node[1]) for node in stack]) break if d 4: cur[2] d 1 nr r dirs[d][0] nc c dirs[d][1] if maze[nr][nc] 0: maze[nr][nc] 2 stack.append([nr, nc, 0]) else: stack.pop() else: print(没有找到路径)Python 版有个小细节stack[-1]取到的是列表对象cur[2] d 1会直接修改栈顶。这个行为和 C 版本的指针操作类似。不要写成r, c, d stack[-1]后只修改局部变量d那样栈里的方向不会更新会导致重复尝试同一个方向。Python 的整数不可变列表元素可变这一点要分清。3.4 Java 版本用 ArrayDeque 而不是老 Stack 类Java 里可以用ArrayDeque当栈。Stack类虽然名字直接但它继承自Vector方法加了同步性能一般新代码里不推荐。import java.util.ArrayDeque; import java.util.Deque; public class MazeStack { static int[][] maze { {1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1}, {1,1,0,1,0,1,0,1}, {1,0,0,0,0,1,0,1}, {1,0,1,1,1,1,0,1}, {1,0,1,0,0,0,0,1}, {1,0,0,0,1,1,0,1}, {1,1,1,1,1,1,1,1} }; static int[] dr {-1, 0, 1, 0}; static int[] dc {0, 1, 0, -1}; static class Node { int row, col, dir; Node(int row, int col, int dir) { this.row row; this.col col; this.dir dir; } } public static void main(String[] args) { int sr 1, sc 1, er 6, ec 6; DequeNode stack new ArrayDeque(); maze[sr][sc] 2; stack.push(new Node(sr, sc, 0)); while (!stack.isEmpty()) { Node cur stack.peek(); if (cur.row er cur.col ec) { System.out.println(找到路径步数: (stack.size() - 1)); for (Node node : stack) { System.out.print(( node.row , node.col ) ); } return; } if (cur.dir 4) { int d cur.dir; cur.dir; int nr cur.row dr[d]; int nc cur.col dc[d]; if (maze[nr][nc] 0) { maze[nr][nc] 2; stack.push(new Node(nr, nc, 0)); } } else { stack.pop(); } } System.out.println(没有找到路径); } }这里ArrayDeque的push等价于addFirstpop等价于removeFirstpeek看栈顶。遍历Deque时顺序是从队头到队尾也就是从栈顶到栈底打印路径时会反过来。如果要按入口到出口顺序打印可以先用另一个栈转一下或者用LinkedList并手动控制。小细节不影响搜索但输出格式要求严格时要注意。3.5 输出路径栈里保存的到底是什么顺序用上面的写法栈底是入口栈顶是当前位置所以从下标 0 到top遍历就是入口到出口的顺序。C 和 Python 版本都能直接打印。Java 的ArrayDeque迭代顺序是从头到尾而push把新元素放在头部所以迭代顺序是出口到入口。要得到入口到出口可以用ArrayDeque的descendingIterator()或者把节点弹到临时列表再反转或者一开始就用addLast、removeLast模拟栈让迭代顺序符合习惯。路径输出还涉及“路径是否包含入口和出口”。一般包含。步数等于坐标数减一。有些题目要求输出方向序列比如“上右下左”那就需要额外记录每次移动的方向。可以在节点里加一个fromDir字段表示“从哪个方向移动到当前格子”打印时根据fromDir反向查字符。3.6 时间复杂度和空间复杂度怎么算在“只找一条路径”且每个格子最多入栈一次的前提下每个格子最多被检查四个方向所以时间复杂度是 O(R × C)其中 R 是行数C 是列数。空间复杂度也是 O(R × C)因为栈最坏情况下可能保存接近所有格子的路径visited 或地图标记也需要 O(R × C) 的空间。如果题目要求输出所有路径复杂度会变成指数级。因为每个岔路口都可能产生多个分支搜索树可能非常庞大。这种场景下显式栈仍然能用但必须允许弹栈时取消访问标记并且要限制搜索深度或路径数量否则很容易跑不完。场景时间复杂度空间复杂度说明找一条路径 DFSO(R×C)O(R×C)每个格子最多访问一次找所有路径指数级O(R×C)需要回溯撤销标记BFS 最短路O(R×C)O(R×C)队列可能同时保存大量节点A* 启发式取决于启发函数O(R×C)最坏仍可能退化为广搜复杂度分析不是写给别人看的装饰它能帮你判断程序为什么慢。如果 100×100 的迷宫跑了几秒还没结果通常是遇到了重复访问、方向没有推进、或者错误地枚举了所有路径。4. 8x8 迷宫实操栈变化与死胡同回退4.1 准备地图和坐标约定还是用上面那张 8x8 地图。入口(1,1)出口(6,6)。坐标(row, col)方向顺序上、右、下、左。起点入栈后标记为 2。栈初始状态栈底 - 栈顶 (1,1,dir0)此时dir0表示下一步尝试上方向。上方向是(0,1)地图值是 1是墙不能走。于是(1,1)的dir变成 1尝试右方向(1,2)地图值是 0可以走。4.2 手工模拟前几步栈如何增长第一步进入(1,2)(1,1,dir1) - (1,2,dir0)在(1,2)上方向(0,2)是墙右方向(1,3)是墙下方向(2,2)是 0进入(2,2)(1,1,dir1) - (1,2,dir2) - (2,2,dir0)在(2,2)上方向(1,2)已访问右方向(2,3)是墙下方向(3,2)是 0进入(3,2)(1,1,dir1) - (1,2,dir2) - (2,2,dir2) - (3,2,dir0)在(3,2)上方向已访问右方向(3,3)是 0进入(3,3)然后(3,4)再尝试上方向(2,4)进入(2,4)再到(1,4)、(1,5)、(1,6)、(2,6)、(3,6)、(4,6)、(5,6)、(6,6)。这条路线会成功。但 DFS 不一定一开始就沿着这条成功路线走。如果某个岔路口先选择了死胡同就会看到弹栈。4.3 死胡同回退的现场记录假设在(3,2)时程序先尝试下方向(4,2)。地图(4,2)是 0进入(1,1) - (1,2) - (2,2) - (3,2) - (4,2)在(4,2)上方向已访问右方向(4,3)是 1下方向(5,2)是 1左方向(4,1)是 0于是进入(4,1)... - (3,2) - (4,2) - (4,1)在(4,1)上方向(3,1)是 0但可能已被访问或未访问右方向(4,2)已访问下方向(5,1)是 0进入(5,1)再到(6,1)、(6,2)、(6,3)、(5,3)、(5,4)、(5,5)、(5,6)、(6,6)。这条路也能成功只是不同。为了看到死胡同弹栈我们可以换一个更明确的局部结构某个格子三面是墙只有来路可走。走到那里后四个方向都不可用栈顶被弹出。假设当前栈是(1,1,dir1) - (1,2,dir2) - (2,2,dir2) - (3,2,dir3) - (3,1,dir0)在(3,1)上方向(2,1)是 1右方向(3,2)已访问下方向(4,1)是 0如果下方向也走不通或者已经探索过那么(3,1)的dir会加到 4随后执行pop。弹出后栈顶变回(3,2)它的dir已经在入栈后继续推进于是尝试下一个方向。这个过程就是回溯。操作栈顶变化说明初始(1,1)入口入栈前进(1,2)右方向可走前进(2,2)下方向可走前进(3,2)下方向可走前进(3,1)左方向可走无路弹出 (3,1)四个方向试完回到岔路栈顶变 (3,2)继续尝试剩余方向4.4 最终路径与输出格式当栈顶坐标等于出口(6,6)时遍历栈即可得到路径。按上面的方向顺序和地图可能得到一条路径(1,1) (1,2) (2,2) (3,2) (3,3) (3,4) (2,4) (1,4) (1,5) (1,6) (2,6) (3,6) (4,6) (5,6) (6,6)步数是 14。路径中每一步都是相邻的上下左右移动且没有经过墙。如果你输出的路径不连续通常是坐标记录顺序错了比如 Java 的ArrayDeque迭代顺序反了。如果路径穿墙通常是地图判断条件写错比如把maze[nr][nc] 0写成了! 1而地图里还有标记 2导致已访问格子被当成通道。输出时可以加上方向字符。比如从(1,1)到(1,2)是右打印R从(3,4)到(2,4)是上打印U。方向和坐标一起输出调试时更直观。5. 常见问题与排查技巧5.1 死循环忘了标记或标记太晚迷宫搜索最常见的 bug 是死循环。程序在几个格子之间来回走栈越来越大最后内存耗尽。原因通常是标记时机不对进入新格子时没有标记导致它被不同邻居反复压栈。弹栈时错误地取消了标记但搜索策略又是“找一条路径”导致其他分支重新进入。方向编号没有推进每次取栈顶都从同一个方向开始压入同一个邻居。排查方法很简单在每次压栈和弹栈时打印push (r,c) dir...和pop (r,c) dir...。如果看到同一个坐标被反复 push基本就是标记或方向问题。小地图上手工跑一遍比盯着代码空想快得多。5.2 栈溢出递归深度、显式栈容量和内存区域“栈溢出”在迷宫问题里可能指三种情况递归版递归太深调用栈不够抛出栈溢出错误。显式栈数组开得太小压入时越界。大数组声明在函数栈上占满线程栈。递归版最危险因为迷宫中可能存在一条很长的蛇形路径递归深度等于路径长度。1000×1000 的迷宫如果路径很长递归深度可能上万。C、Java、Python 的默认递归深度限制不同Python 默认大约 1000 层很容易触发RecursionError。解决办法是改用显式栈或者手动调大递归限制但后者不治本。显式栈版要注意容量。最坏情况下栈大小可能达到R × C所以容量至少开到R * C 1。C 语言里用malloc动态分配或者把栈数组设为全局Java 用ArrayDeque会自动扩容Python 列表也会自动扩容。Java 中还要区分堆和栈new Node()对象在堆上ArrayDeque也在堆上方法调用帧在虚拟机栈上。堆内存不足会抛OutOfMemoryError虚拟机栈不足会抛StackOverflowError两者排查方向不同。5.3 找到的路径不是最短DFS 本来就不保证很多人第一次用栈跑完迷宫发现路径绕了一大圈就怀疑代码有 bug。其实 DFS 只保证“找到一条路”不保证“最短”。它的策略是沿一个方向深入到底撞墙再回退。迷宫如果有环DFS 可能先钻一条很长的分支最后才找到出口。要最短路径应该用 BFS。BFS 按层扩展第一次到达出口时经过的步数一定最少。BFS 用队列不用栈。队列是先进先出先进入的节点先扩展所以它能一圈一圈地向外搜索。A* 则是在 BFS 基础上加入启发函数适合大地图游戏寻路。栈适合做回溯、表达式求值、括号匹配、函数调用模拟求最短路时不要硬套。5.4 路径丢失弹栈时把有效路径也删了显式栈保存的是当前搜索路径。如果弹栈逻辑写错比如找到出口后继续弹栈或者弹栈后没有回到正确岔路口路径就可能丢失。常见原因是把“当前节点”和“栈顶节点”混用。在循环中如果先pop再检查出口肯定找不到。正确顺序是先看栈顶判断是否出口再决定尝试方向或弹栈。另一个坑是路径记录和搜索栈分开维护。有些人用一个path列表记录路径又用一个stack做搜索但两者没有同步。弹栈时只弹了stack没弹path最后path里会混入死胡同。要么让搜索栈直接保存路径要么严格同步两个结构。5.5 常见问题速查表现象可能原因解决思路程序死循环未标记访问方向编号未推进入栈时标记尝试后dir压栈越界栈容量小于 R×C容量开到 R×C1 或动态扩容递归报错递归深度过大改用显式栈或限制地图规模路径穿墙可走判断写错只允许maze[nr][nc] 0路径不连续输出顺序反了或路径混入死胡同检查栈迭代顺序和弹栈同步找不到出口出口在墙上、入口标记错、方向数组错打印入口出口值手工走两步路径不是最短用了 DFS改 BFS 或 A*Java 输出反向ArrayDeque 迭代顺序是栈顶到栈底用 descendingIterator 或临时栈5.6 我踩过的几个坑第一个坑是方向数组写成了{0,1},{1,0},{0,-1},{-1,0}以为是上右下左实际是右、下、左、上。代码能跑路径也合法但和手工模拟对不上查了很久才发现顺序问题。后来我固定用注释标清楚每个方向编号省了很多事。第二个坑是在弹栈时取消了地图上的访问标记。当时想“既然回退了这个格子以后也许还能从别的路走”结果程序在环里绕不出来。找一条路径时访问标记表示“这个格子已经确认探索过”不需要取消。只有枚举所有路径时才需要恢复现场。两种目标对应两种标记策略不能混。第三个坑是 C 语言里把StackNode stack[1000000]写在main函数里编译没问题运行直接崩溃。后来改成全局数组或malloc就好了。这个坑和算法无关但新手很容易遇到尤其是从 Python 转 C 的时候。6. 进阶优化与工程化扩展6.1 剪枝和方向启发让 DFS 少走冤枉路DFS 在迷宫里的效率通常够用但如果地图很大、死胡同很多可以通过剪枝减少无效分支。剪枝算法的核心思想是在进入某个格子之前先用简单规则判断它是否可能通向出口。比如如果某个通道格子的上下左右都被墙或已访问格子包围它不可能继续前进可以提前跳过。如果某个区域与出口不连通可以先做连通性标记只搜索连通区域。按曼哈顿距离给方向排序优先尝试离出口更近的方向。曼哈顿距离是abs(row - er) abs(col - ec)。在尝试四个方向时可以先把可走方向按距离从小到大排序再依次入栈。这样 DFS 会更早靠近出口但不保证最短。这个方法在游戏寻路里很常见配合 A* 效果更好。剪枝不会改变算法的正确性前提是剪枝规则不能误删可行路径。比如“某格子四面被墙包围”这种判断是安全的“某格子看起来离出口远”不能直接删只能调整顺序。工程里宁可少剪一点也不要为了速度引入错误。6.2 栈、队列、优先队列分别对应什么算法数据结构搜索策略适合问题栈深度优先搜索回溯、连通性、找一条路径队列广度优先搜索无权图最短路、最少步数优先队列A*、Dijkstra带权图、启发式寻路递归调用栈深度优先搜索代码简洁的回溯栈和队列经常被放在一起讲因为它们的区别就是进出顺序。栈是后进先出队列是先进先出。迷宫问题里把栈换成队列搜索行为就从“一条路走到黑”变成“一圈一圈往外扩”。如果你把代码里的pop改成popleft再把压栈改成入队很可能就得到了 BFS 版本。但要注意BFS 找到出口时不能立即返回吗可以因为 BFS 按层扩展第一次到达出口就是最短路径。6.3 多入口、多出口和动态迷宫怎么处理多入口迷宫的思路是把所有入口先压入栈并标记为已访问。然后正常搜索找到任意出口就结束。如果要求“从最近入口到最近出口”那就不能用普通 DFS应该用多源 BFS所有入口同时入队第一次碰到出口时就是最少步数。多出口也类似。如果只要求找到一个出口正常搜索即可如果要求最近出口用 BFS 或 A*。动态迷宫指搜索过程中障碍会变化比如游戏里的门会开关。这种场景需要把“时间”或“状态”加入节点同一个坐标在不同时间可能是不同状态。搜索空间会变大通常要用带状态的 BFS 或 A*。工程化时建议把地图表示、方向定义、搜索算法分开。地图模块只负责判断某个坐标是否可走搜索模块只负责压栈、弹栈、访问标记输出模块只负责把路径转成坐标序列或方向字符串。这样换地图、换算法、换输出格式时不会互相牵连。6.4 用日志和可视化把栈的变化看清楚学习栈应用时最有效的方法不是盯着代码而是把栈的变化打印出来。可以在每次循环开头打印step12 top(3,2,dir2) stack_size4 try dir2 - (4,2) push (4,2,dir0)也可以把已访问格子标记为.当前路径标记为*出口标记为E每走一步打印一次地图。小地图上肉眼就能看出程序有没有走错。对于 8x8 迷宫打印 20 步左右就能定位大部分逻辑错误。可视化不一定要做图形界面。终端字符输出就够用。关键是让“栈顶、方向、访问标记、当前路径”四个信息同时可见。很多 bug 之所以难查是因为只能看到最终结果看不到中间状态。把中间状态暴露出来问题往往自己就浮出来了。6.5 从课堂作业到小项目还能怎么扩展迷宫问题可以做得很小也可以继续扩展。比如加一个随机迷宫生成器用深度优先搜索挖通道加一个路径动画用字符逐帧播放加一个关卡编辑器让用户手动改地图或者把搜索算法封装成库在游戏项目里复用。全栈项目里如果需要做简单的寻路演示后端返回迷宫矩阵前端用 Canvas 画格子和路径栈搜索过程可以作为每一步的动画数据返回。如果想让程序更稳可以写几个小测试入口在出口旁边期望步数为 1出口不可达期望返回失败入口是墙期望报错只有一个格子的迷宫期望步数为 0。测试不需要复杂框架一个主函数里多跑几个用例就行。我自己的习惯是先用小地图验证逻辑再用大地图测性能和内存。小地图上手工能算出的结果是最可靠的断言。最后再分享一个实际带新人时的做法不要一上来就写完整代码先让他在纸上画一个 5x5 迷宫然后每一步写出栈里有什么、栈顶方向编号是多少。能手工把死胡同回退画明白的人写代码时基本不会犯方向不推进、标记时机错误这类问题。栈的应用说到底不是语法而是你对“路径”和“回退”这两个动作的理解。