迷宫问题指南
算法迷宫网格DFSBFS
迷宫问题指南
目录
核心概念
迷宫问题本质上是二维网格上的搜索问题，核心技巧：
| 要素 | 说明 |
|---|---|
| 网格表示 | grid[row][col]，grid[y][x]（先 row 再 col） |
| 方向数组 | [[1,0], [-1,0], [0,1], [0,-1]]（上下左右） |
| 越界检查 | x<0 || x>=cols || y<0 || y>=rows |
| 访问标记 | 原地修改（grid[y][x]='0'）或 visited[][] |
| 两种搜索 | DFS（递归/栈）适合连通区域；BFS（队列）适合最短路径 |
通用解题模板
DFS 模板（递归）
function solveDFS(grid: string[][]): number {
const rows = grid.length;
if (rows === 0) return 0;
const cols = grid[0].length;
// 方向数组：右、左、下、上
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function dfs(x: number, y: number): void {
// 1. 越界检查
if (x < 0 || x >= cols || y < 0 || y >= rows) return;
// 2. 障碍/已访问检查
if (grid[y][x] === '0') return;
// 3. 处理当前格子
grid[y][x] = '0'; // 标记已访问（淹没法）
// 4. 四个方向递归
for (const [dx, dy] of DIRS) {
dfs(x + dx, y + dy);
}
}
// 5. 主逻辑：遍历每个格子
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
if (grid[y][x] === '1') {
// 处理入口逻辑
dfs(x, y);
}
}
}
}BFS 模板（队列）
function solveBFS(grid: string[][]): number {
const rows = grid.length;
if (rows === 0) return 0;
const cols = grid[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function bfs(startX: number, startY: number): void {
const queue: [number, number][] = [[startX, startY]];
grid[startY][startX] = '0'; // 入队即标记
while (queue.length > 0) {
const [x, y] = queue.shift()!;
for (const [dx, dy] of DIRS) {
const nx = x + dx;
const ny = y + dy;
// 越界 + 障碍检查
if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) continue;
if (grid[ny][nx] === '0') continue;
grid[ny][nx] = '0'; // 标记
queue.push([nx, ny]);
}
}
}
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
if (grid[y][x] === '1') {
bfs(x, y);
}
}
}
}DFS vs BFS 选择指南
需要统计连通块数量/面积 → DFS（代码更短）
需要求最短路径/最少步数 → BFS（逐层扩散，天然最短）
网格极大可能栈溢出 → BFS（迭代，无递归栈风险）
需要记录路径本身 → BFS（配合 parent 映射回溯）例题 1：岛屿数量
LeetCode 200 — 统计网格中连通 ‘1’ 区域的数量
输入: grid = [
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3思路： 遍历网格，遇到 '1' 计数 +1，然后 DFS/BFS 淹没整个岛屿（把相连的 '1' 全改成 '0'）。
DFS 淹没法图解：
遇 '1' → count=1 淹没整个岛 继续扫描
┌─────────┐ ┌─────────┐ ┌─────────┐
│1 1 0 0 0│ │0 0 0 0 0│ │0 0 0 0 0│
│1 1 0 0 0│ → │0 0 0 0 0│ → │0 0 1 0 0│ count=2
│0 0 1 0 0│ │0 0 1 0 0│ │0 0 0 0 0│
│0 0 0 1 1│ │0 0 0 1 1│ │0 0 0 1 1│
└─────────┘ └─────────┘ └─────────┘function numIslands(grid: string[][]): number {
const rows = grid.length;
if (rows === 0) return 0;
const cols = grid[0].length;
let count = 0;
function dfs(x: number, y: number): void {
if (x < 0 || x >= cols || y < 0 || y >= rows) return;
if (grid[y][x] === '0') return;
grid[y][x] = '0'; // 淹没
dfs(x + 1, y);
dfs(x - 1, y);
dfs(x, y + 1);
dfs(x, y - 1);
}
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
if (grid[y][x] === '1') {
count++;
dfs(x, y);
}
}
}
return count;
}复杂度： 时间 O(m×n)，空间 O(m×n)（递归栈最坏情况）。
例题 2：迷宫是否有路径
判断从起点 (0,0) 能否走到终点 (m-1, n-1)，
0可走，1是墙
输入: maze = [
[0, 0, 1, 0],
[1, 0, 0, 1],
[0, 0, 0, 0],
[0, 1, 0, 0]
]
输出: true（存在路径）思路： 从起点 DFS/BFS，标记访问过的格子，看能否到达终点。
function hasPath(maze: number[][]): boolean {
const rows = maze.length;
if (rows === 0) return false;
const cols = maze[0].length;
const visited: boolean[][] = Array.from({ length: rows }, () =>
new Array(cols).fill(false)
);
function dfs(x: number, y: number): boolean {
// 越界或撞墙或已访问
if (x < 0 || x >= cols || y < 0 || y >= rows) return false;
if (maze[y][x] === 1 || visited[y][x]) return false;
// 到达终点
if (x === cols - 1 && y === rows - 1) return true;
visited[y][x] = true;
// 四方向搜索，任一方向到达即返回 true
return (
dfs(x + 1, y) ||
dfs(x - 1, y) ||
dfs(x, y + 1) ||
dfs(x, y - 1)
);
}
return dfs(0, 0);
}注意： 这里用 visited[][] 而非原地修改，因为需要保留原迷宫数据。DFS 的返回值用 || 短路求值，一旦找到终点就不再继续搜索。
例题 3：迷宫最短路径
求从起点到终点的最短路径长度（步数），
0可走，1是墙，无法到达返回 -1
输入: maze = [
[0, 0, 0, 0],
[1, 1, 0, 1],
[0, 0, 0, 0],
[0, 1, 1, 0]
]
输出: 6 （最短路径需要 6 步）思路： 必须用 BFS，因为 BFS 逐层扩散，第一次到达终点就是最短路径。
function shortestPath(maze: number[][]): number {
const rows = maze.length;
if (rows === 0) return -1;
const cols = maze[0].length;
// 起点或终点是墙
if (maze[0][0] === 1 || maze[rows - 1][cols - 1] === 1) return -1;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const queue: [number, number, number][] = [[0, 0, 0]]; // [x, y, steps]
const visited: boolean[][] = Array.from({ length: rows }, () =>
new Array(cols).fill(false)
);
visited[0][0] = true;
while (queue.length > 0) {
const [x, y, steps] = queue.shift()!;
// 到达终点
if (x === cols - 1 && y === rows - 1) return steps;
for (const [dx, dy] of DIRS) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) continue;
if (maze[ny][nx] === 1 || visited[ny][nx]) continue;
visited[ny][nx] = true;
queue.push([nx, ny, steps + 1]);
}
}
return -1; // 无法到达
}BFS 逐层扩散过程（数字 = 步数）：
0 → 1 → 2 → 3
↓
→ 4 → 5 → 6（终点！）为什么 DFS 不行？ DFS 找到的第一条路径不一定是最近的，需要遍历所有路径取最小值，效率低。
例题 4：岛屿的最大面积
LeetCode 695 — 返回网格中最大的岛屿面积（连通 ‘1’ 的数量）
输入: grid = [
[0,0,1,0,0],
[0,1,1,1,0],
[0,0,1,0,0],
[1,1,0,0,0]
]
输出: 5 （中间十字形岛屿面积=5）function maxAreaOfIsland(grid: number[][]): number {
const rows = grid.length;
if (rows === 0) return 0;
const cols = grid[0].length;
let maxArea = 0;
function dfs(x: number, y: number): number {
if (x < 0 || x >= cols || y < 0 || y >= rows) return 0;
if (grid[y][x] === 0) return 0;
grid[y][x] = 0; // 淹没
// 返回当前格子(1) + 四个方向的面积之和
return (
1 +
dfs(x + 1, y) +
dfs(x - 1, y) +
dfs(x, y + 1) +
dfs(x, y - 1)
);
}
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
if (grid[y][x] === 1) {
maxArea = Math.max(maxArea, dfs(x, y));
}
}
}
return maxArea;
}关键技巧： DFS 返回 int 类型，累加四方向面积 + 当前格子 1，天然得到连通块大小。
例题 5：传送门迷宫
迷宫中有若干传送门，进入传送门会瞬间传送到另一个传送门位置。求从起点到终点的最短路径。
输入: maze = [
[0, 0, 0, 0],
[0, 9, 0, 1],
[1, 0, 0, 0],
[0, 0, 9, 0]
]
起点: (0,0), 终点: (3,3)
0=空地, 1=墙, 9=传送门图解：
(0,0) → (0,1) → (0,2) → (1,2)
↓ ↓
(1,1)[9] ←←←←←← 传送 ←←←← (3,2)[9]
↓
(2,1) → (2,2) → (2,3) → (3,3)终点
不走传送门：约 9 步
走传送门： 7 步（进入 9 后瞬移到另一个 9）思路： 先记录所有传送门坐标，BFS 时遇到传送门，除了走四方向外，还能零代价传送到其他传送门。
关键点
- 传送门预处理：遍历迷宫，把所有
9的坐标收集到一个数组 - BFS 扩展：当前格子是传送门时，将其他所有传送门坐标入队（步数 +1）
- 传送门只能使用一次：传送到目标传送门后，从目标出发时不再传送（避免无限循环），标记已使用
function shortestPathWithPortal(maze: number[][]): number {
const rows = maze.length;
if (rows === 0) return -1;
const cols = maze[0].length;
const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];
// 1. 收集所有传送门坐标
const portals: [number, number][] = [];
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
if (maze[y][x] === 9) {
portals.push([x, y]);
}
}
}
// 起点或终点是墙
if (maze[0][0] === 1 || maze[rows - 1][cols - 1] === 1) return -1;
const queue: [number, number, number][] = [[0, 0, 0]]; // [x, y, steps]
const visited: boolean[][] = Array.from({ length: rows }, () =>
new Array(cols).fill(false)
);
visited[0][0] = true;
// 标记传送门是否已使用（入队过一次就不再传送）
let portalUsed = false;
while (queue.length > 0) {
const [x, y, steps] = queue.shift()!;
// 到达终点
if (x === cols - 1 && y === rows - 1) return steps;
// 2. 当前格子是传送门，且传送门还没被用过
if (maze[y][x] === 9 && !portalUsed) {
portalUsed = true;
for (const [px, py] of portals) {
// 跳过自己
if (px === x && py === y) continue;
if (!visited[py][px]) {
visited[py][px] = true;
queue.push([px, py, steps + 1]); // 传送花费 1 步
}
}
}
// 3. 正常的四方向移动
for (const [dx, dy] of DIRS) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) continue;
if (maze[ny][nx] === 1 || visited[ny][nx]) continue; // 墙或已访问
visited[ny][nx] = true;
queue.push([nx, ny, steps + 1]);
}
}
return -1; // 无法到达
}
// 测试
const maze = [
[0, 0, 0, 0],
[0, 9, 0, 1],
[1, 0, 0, 0],
[0, 0, 9, 0]
];
console.log(shortestPathWithPortal(maze)); // 输出: 7传送门变体讨论
┌──────────────────────────────────────────────────────────────┐
│ 变体 处理方式 │
├──────────────────────────────────────────────────────────────┤
│ 传送门可反复使用 去掉 portalUsed 标记 │
│ 多组传送门（不同颜色配对） 用 Map<color, coords[]> 分组 │
│ 传送花费 0 步 入队时 steps 不加 1 │
│ 传送门单次使用后消失 传送后把 maze[y][x] 改为 0 │
│ 传送门是单向的 portals 存为 {from: [x,y], to: [x,y]}│
└──────────────────────────────────────────────────────────────┘复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间 | O(m×n + P²)，P 为传送门数量（传送时遍历所有传送门） |
| 空间 | O(m×n)（visited 数组 + 队列） |
优化： 如果传送门很多，可以建图将传送门之间的关系预处理为邻接表，BFS 时直接查表 O(1)。
常见变形与技巧
1. 八方向（含对角线）
const DIRS_8 = [
[1, 0], [-1, 0], [0, 1], [0, -1], // 四方向
[1, 1], [1, -1], [-1, 1], [-1, -1], // 对角线
];2. 用 visited 数组 vs 原地修改
| 方式 | 优点 | 缺点 |
|---|---|---|
原地修改 grid[y][x]='0' |
省空间 | 破坏原数据 |
visited[][] 布尔数组 |
保留原数据 | 额外 O(m×n) 空间 |
3. 避免递归栈溢出
网格极大（如 1000×1000 全是 ‘1’）时，DFS 递归可能栈溢出：
// 方案1：改用 BFS
// 方案2：手动栈模拟 DFS
function dfsStack(grid: string[][], startX: number, startY: number): void {
const stack: [number, number][] = [[startX, startY]];
while (stack.length > 0) {
const [x, y] = stack.pop()!;
// ... 四方向处理
}
}4. 多源 BFS（如“腐烂的橘子”）
// 多个起点同时入队，并行扩散
const queue: [number, number][] = [];
for (let y = 0; y < rows; y++) {
for (let x = 0; x < cols; x++) {
if (grid[y][x] === 2) { // 所有腐烂橘子入队
queue.push([x, y]);
}
}
}
// 然后统一 BFS5. 常见题型对照
| LeetCode | 题目 | 技巧 |
|---|---|---|
| 200 | 岛屿数量 | DFS/BFS 淹没法 |
| 695 | 岛屿最大面积 | DFS 返回面积 |
| 463 | 岛屿周长 | 遇水/边界 +1 |
| 130 | 被围绕的区域 | 边界 DFS + 标记法 |
| 994 | 腐烂的橘子 | 多源 BFS |
| 490 | 迷宫 | DFS + 一直走到撞墙 |
| 1091 | 二进制矩阵最短路径 | BFS 最短路径 |
| 1254 | 封闭岛屿数量 | 先淹边界岛，再统计内部 |
总结
迷宫问题的核心就是：方向数组 + 越界检查 + 访问标记
DFS（递归/栈） BFS（队列）
┌──────────────┐ ┌──────────────┐
│ 连通块计数 │ │ 最短路径 │
│ 岛屿数量 │ │ 最少步数 │
│ 岛屿面积 │ │ 迷宫最短路 │
│ 路径存在性 │ │ 多源扩散 │
└──────────────┘ └──────────────┘
口诀：
遇 '1' 先计数，DFS 淹没全岛
求最短路用 BFS，逐层扩散天然短
方向数组记心间，越界标记不能忘关联题库
以下题目与本文知识点相关，可以跳转到题库练习：