LeetCode 490. 迷宫
题目描述
✅ 490. 迷宫
题意分析
球选择一个方向后，会一直滚到下一格是墙或越界的位置才停止，停下后才能重新选择方向。需要判断能否最终停在目标格；滚动过程中经过目标格，不代表能够停在那里。
解法：停点 BFS
核心思路
[!blue]
每次停下的位置决定了接下来能选择哪些滚动方向，因此把停点作为图中的节点，把一次完整滚动作为一条边。起点也是初始停点。从某个停点出发，沿四个方向分别模拟到不能继续移动，就得到它的全部后继状态。
用 BFS 遍历这张图：先将起点标记并入队，再不断取出停点、生成它的后继。相同停点的后续选择始终相同，所以第一次发现时就标记，之后无需重复搜索；贴墙方向滚动零步得到自身，也会被已有标记过滤。
滚动时始终先检查下一格，只有合法且为空地才向前移动。循环结束时，当前位置仍在空地上，而下一步已经受阻，恰好就是这次滚动的停点。中途经过的格子不进入队列，也不用于判断成功。
任意可行路线都能拆成这些完整滚动，BFS 会逐个扩展所有可达停点，所以找到终点就返回
true，队列耗尽仍未找到则返回false。本题只判断可达性，一次滚动经过多少格不会影响搜索顺序的正确性。
解题步骤
- 创建访问表和队列，标记起点并入队。
- 取出队头，若等于终点则返回
true；起点等于终点也会在这里直接成功。- 对四个方向分别调用滚动过程，得到最终停点。
- 停点尚未访问时，立即标记并入队。
- 队列为空后返回
false。
代码实现
class Solution {
// 从某个停点出发有四个方向，每个方向需要模拟滚动直到下一步越界或遇墙。
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new ArrayDeque<>();
visited[start[0]][start[1]] = true;
queue.offer(new int[] {
start[0],
start[1]
});
int[][] dirs = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (cur[0] == destination[0] && cur[1] == destination[1]) {
return true;
}
for (int[] dir : dirs) {
// 整次滚动结束的位置才是可入队状态
int[] next = roll(maze, cur[0], cur[1], dir);
if (visited[next[0]][next[1]]) {
continue;
}
// 发现停点即标记，重复方向与零步自环不再展开
visited[next[0]][next[1]] = true;
queue.offer(next);
}
}
return false;
}
private int[] roll(int[][] maze, int row, int col, int[] dir) {
int m = maze.length;
int n = maze[0].length;
while (canMove(maze, row + dir[0], col + dir[1], m, n)) {
row += dir[0];
col += dir[1];
}
return new int[] {
row,
col
};
}
private boolean canMove(int[][] maze, int row, int col, int m, int n) {
return row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == 0;
}
}
func hasPath(maze [][]int, start []int, destination []int) bool {
// 从某个停点出发有四个方向，每个方向需要模拟滚动直到下一步越界或遇墙。
m, n := len(maze), len(maze[0])
visited := make([][]bool, m)
for i := 0; i < m; i++ {
visited[i] = make([]bool, n)
}
queue := make([][2]int, 0)
queue = append(queue, [2]int{
start[0],
start[1],
})
visited[start[0]][start[1]] = true
dirs := [][2]int{
{1, 0},
{-1, 0},
{0, 1},
{0, -1},
}
roll := func(row, col int, dir [2]int) [2]int {
for {
nextRow := row + dir[0]
nextCol := col + dir[1]
if nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n {
break
}
if maze[nextRow][nextCol] == 1 {
break
}
row = nextRow
col = nextCol
}
return [2]int{
row,
col,
}
}
for head := 0; head < len(queue); head++ {
cur := queue[head]
if cur[0] == destination[0] && cur[1] == destination[1] {
return true
}
for _, dir := range dirs {
// 整次滚动结束的位置才是可入队状态
next := roll(cur[0], cur[1], dir)
if visited[next[0]][next[1]] {
continue
}
// 发现停点即标记，重复方向与零步自环不再展开
visited[next[0]][next[1]] = true
queue = append(queue, next)
}
}
return false
}
复杂度分析
- 时间复杂度：$O(mn\max(m,n))$。矩阵有 $m$ 行、$n$ 列，至多展开 $mn$ 个停点，每个停点向四个方向滚动，单次最多扫描一行或一列。
- 空间复杂度：$O(mn)$，访问表与队列。
关键点总结
[!green]
- 状态是停点，不是每个经过的空格。
- 贴墙方向得到自身，已有访问标记会过滤这条无用边。
易错点总结
[!yellow]
- 把相邻空格直接入队，会允许球中途刹车。
- 把途经终点当作成功，会接受无法停留的位置。
- 滚动之前不检查下一格，会越过边界或停进墙里。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 505. 迷宫 II | 中等 | 滚动到墙才停止的规则相同，原题还需最小化实际走过格子数，边权不再统一。 |
| 499. 迷宫 III | 困难 | 原题遇洞可提前停止且要选最短字典序路径，本题只判断能否恰好停在目标。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！