迷宫寻路
回溯与搜索 · 网格搜索
在迷宫里找一条路
给一张带墙的方格地图，从起点出发，找一条通往终点的路。这是回溯最形象的一幕：像一只老鼠 🐭 在迷宫里走——挑一个方向往前走，走到死胡同就退回上一个路口，换一个方向再试，直到走到终点。前几页的回溯画在棋盘和决策树上，这一页画在网格上。
深度优先 + 回溯
做法是深度优先搜索（DFS）：站在一格，按固定顺序（比如下、右、上、左）尝试四个方向；遇到墙、越界或走过的格就跳过，否则迈过去、把新格标记为已访问（防止绕圈），然后在新格上递归地重复。如果一格四个方向都走不通，说明这是死路——回溯：退回上一格，接着试它剩下的方向。
「标记已访问」是关键：没有它，老鼠会在两格之间来回打转、永远走不完。下面是一张 5×5 迷宫（S 起点、🚩 终点、深色是墙）。点「下一步」逐步看：🐭 是当前位置、琥珀色是当前尝试的路径、浅蓝色是走过又放弃的格；留意老鼠几次撞进死路又退回来。走到终点时，整条解路径变绿。右侧代码随每一步同步高亮。
🐭
🚩
从起点 (0,0) 出发，找终点 (4,4)
1function solveMaze(grid: number[][], sr: number, sc: number, gr: number, gc: number) {
2 const visited = new Set<string>();
3 const path: [number, number][] = [];
4 const dfs = (r: number, c: number): boolean => {
5 const key = r + ',' + c;
6 if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return false;
7 if (grid[r][c] === 1 || visited.has(key)) return false; // 墙 / 已访问
8 visited.add(key);
9 path.push([r, c]); // 走到 (r,c)
10 if (r === gr && c === gc) return true; // 到达终点
11 for (const [dr, dc] of [[1,0],[0,1],[-1,0],[0,-1]]) { // 四个方向
12 if (dfs(r + dr, c + dc)) return true;
13 }
14 path.pop(); // 死路 → 回溯，退回上一格
15 return false;
16 };
17 dfs(sr, sc);
18 return path;
19}
起点(0,0)
终点(4,4)
当前格(0,0)
路径长1
已访问1
1 / 19
DFS 找到的是一条路，未必是最短的。要找最短路，换成广度优先搜索（BFS）——一圈圈地扩散、第一次碰到终点就是最短；但那属于「搜索」的另一支，不再是回溯。想找所有路径，则和其它回溯题一样：找到一条后不停下、继续回溯。
网格搜索：回溯的第三种形态
至此回溯与搜索大类的三种状态空间都齐了：
棋盘约束：N 皇后。决策树枚举：子集 / 全排列 / 组合总和。
网格搜索：迷宫寻路（本页）。同类还有：岛屿数量、单词搜索、扫雷展开——都是网格上的 DFS/BFS；想让搜索「认路」，见 A* 寻路。
棋盘约束：N 皇后。决策树枚举：子集 / 全排列 / 组合总和。
网格搜索：迷宫寻路（本页）。同类还有：岛屿数量、单词搜索、扫雷展开——都是网格上的 DFS/BFS；想让搜索「认路」，见 A* 寻路。
同一套「深入 → 受阻 → 回退」的骨架，套在棋盘、决策树、网格等不同的状态空间上，就是回溯与搜索解决一大类问题的通用思路。