LeetCode 490. 迷宫

2024-05-22 HGNULB 约 9 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 490. 迷宫

题意分析

网格里 0 是空地、1 是墙。球从起点开始，每次选定一个方向后就一直滚，直到下一格是墙或越出边界才停下，中途不能改向也不能刹车。问的是能否让球恰好停在终点，返回布尔值。

「停」这个字是全题的关键。球路过终点不算数，必须是撞墙后静止的位置正好等于终点。这意味着解空间不是所有空地，而是所有「可停位置」的集合。

与需要计算最短距离的变体不同，本题只问可达性，不关心走了多少格，也不关心用了几次滚动。这直接决定了不需要任何带权最短路的机制，一次普通的图遍历就够。

边界情况：起点本身就是终点时应当返回真；球在某个方向上紧贴墙壁，一格也滚不动，停点就是自己；终点若位于一条通道的中段且两侧都不是墙，球永远停不下来，此时必须返回假。

解法：停点 BFS

核心思路

如果按普通网格题的习惯，把「相邻空地」当作边去做遍历，会立刻出错——球没有停在相邻格的能力，那些格子不是合法状态。所以第一步必须重新定义图：节点是球能够静止的格子，一条边表示从某个停点选定一个方向滚到下一个停点。

有了这个定义，问题就退化成最朴素的图可达性：从起点这个节点出发，能否走到终点这个节点。可达性对遍历顺序没有要求，广度优先和深度优先都行，这里用队列实现的广度优先，写法上不用担心递归深度。

每个停点最多引出四条边，边的另一端靠模拟得到：沿方向一格一格试探，直到下一格越界或是墙就停，此时手里的坐标就是停点。注意贴墙时试探一次就退出，停点等于出发点，这条自环边不会带来新状态，被访问标记自动过滤掉。

维持的不变量是：访问标记只打在停点上，且入队即标记。前半句保证滚动途中经过的格子不会被误当成状态，后半句保证每个停点最多进队一次，遍历必然终止。终点判断放在出队时（或入队时，二者等价），队列排空仍未命中就说明不可达。

解题步骤

建一个与网格同形的访问标记矩阵，把起点标记为已访问并入队。起点是天然的停点——球放在那里本来就是静止的。

循环从队头取出一个停点，先判断它是否等于终点，是就直接返回真。判断放在出队时最省心，因为起点自身也会走这条分支，天然覆盖了「起点即终点」的边界。

对四个方向各做一次滚动模拟。模拟写成「先算下一格，越界或是墙就退出循环，否则真正移动过去」，退出时的坐标必然是合法的停点，不需要额外回退一步。

得到停点后先查访问标记，已访问就跳过。跳过的情形包括两类：一是贴墙滚不动导致停点是自己，二是这个停点已由别的路径到达过，两类都无需重复展开。

未访问的停点立刻打标记并入队。标记必须在入队时打，如果推迟到出队再打，同一个停点会被多个方向重复推入队列，最坏情况下队列规模成倍膨胀。

队列排空仍未命中终点，说明终点不在可停位置的连通分量里，返回假。

以 maze = [[0,0,0],[1,1,0],[0,0,0]]、start = [0,0]、destination = [2,0] 走一遍：队列初始为 [(0,0)]，已访问集合为 {(0,0)}。方向顺序取下、上、右、左。

出队 (0,0)，不是终点。向下试探 (1,0) 是墙，一格没动，停点仍是 (0,0)，已访问，跳过。向上试探越界，停点还是自己，跳过。向右：(0,1) 是空地移过去，(0,2) 是空地再移过去，(0,3) 越界，停在 (0,2)，未访问，标记入队。向左试探越界，跳过。此时队列为 [(0,2)]。

出队 (0,2)，不是终点。向下：(1,2) 空地、(2,2) 空地、(3,2) 越界，停在 (2,2)，标记入队。向上越界停在自己，跳过。向右越界停在自己，跳过。向左：一路滚回 (0,0)，已访问，跳过。队列为 [(2,2)]。

出队 (2,2)，不是终点。向下、向右都越界停在自己。向上滚回 (0,2)，已访问。向左：(2,1)、(2,0)、再往左越界，停在 (2,0)，标记入队。队列为 [(2,0)]。

出队 (2,0)，它正是终点，返回真。

若把终点改成 (2,1)，同样的搜索会把 (0,0)、(0,2)、(2,2)、(2,0) 四个停点全部访问完，队列排空也没命中——因为 (2,1) 处在底部通道的中间，球从左右两侧滚过时都不会停在那里，此时返回假，这正是本题必须用停点而非空地建模的原因。

代码实现

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(m \cdot n \cdot \max(m, n))$，最多有 $m \cdot n$ 个停点入队，每个停点展开四个方向，单次滚动最坏要扫过一整行或一整列，也就是 $\max(m, n)$ 格。

空间复杂度：$O(m \cdot n)$，访问标记矩阵与网格同形，队列在最坏情况下会同时容纳所有停点，两者都是网格规模。

关键点总结

移动规则不是「走一格」时，先重新定义节点和边，再套遍历模板。本题的节点是停点、边是一次完整滚动，想清楚这一层，剩下的就是标准图搜索。

只问可达性就不要引入距离机制。广度优先与深度优先在这里完全等价，选队列版仅仅是为了避开深递归。

访问标记的粒度必须与状态定义一致。把滚动途中的格子也标记上，等于承认了不存在的状态，答案会偏松。

贴墙时停点等于出发点，这条自环由访问标记自然吸收，不需要专门写特判——识别出这一点能省掉一段容易写错的代码。

面试视角：开口先讲「为什么不能按相邻格建图」，这是面试官真正想听的判断。写完后主动补一句「若改问最少经过格数，边权就不再相同，得换成 Dijkstra」，能直接把话题接到 505 上，展示出对题型谱系的掌握。

易错点总结

错误写法：按普通网格题把四个相邻空地当作邻居入队。maze = [[0,0,0],[1,1,0],[0,0,0]]、终点 (2,1) → 会认为球能停在通道中段而返回真，正确答案是假。

错误写法：把滚动途中经过的每个格子都打上访问标记。同一用例 → 中间格子被当成已访问的状态，既污染了状态空间，又可能挡住后续从其他方向到达的真实停点。

错误写法：滚动时先移动再判断合法性。球贴着第 0 行向上滚 → 直接读到下标 -1，抛出数组越界异常。

错误写法：滚动循环写成「移动到越界为止再回退一步」，但回退条件与撞墙情形不统一。撞墙时会回退到墙里或多退一格，得到根本不存在的停点。

错误写法：把访问标记推迟到出队时才打。存在多条路径汇聚到同一停点的迷宫 → 该停点被重复入队，队列规模成倍增长，大网格上明显变慢。

错误写法：滚动结果等于出发点时不做任何处理就入队。任意用例 → 球贴墙的方向会把自己反复推进队列，形成死循环。

错误写法：只在入队时判断是否为终点，却没有对起点做同样的判断。start 与 destination 相同 → 起点是直接入队的，绕过了判断，最终返回假，正确答案是真。

错误写法：假设网格是方阵，用同一个长度同时校验行下标和列下标。maze = [[0,0,0,0]] 这类扁平网格 → 合法的列下标被误判为越界，球提前「停」在错误位置。

错误写法：认为球必须移动至少一格才算到达终点。起点即终点的用例 → 返回假；正确答案是真，因为球本来就停在那里。

相似题目

题目	难度	考察点
505. 迷宫 II	中等	同样的停点建模，但要最少经过格数，须改用 Dijkstra
499. 迷宫 III	困难	多出一个洞口会吸走球，且答案要按指令字典序排序
200. 岛屿数量	中等	标准的单步四连通连通块统计，可用来对照建图差异
1091. 二进制矩阵中的最短路径	中等	八连通单步移动，边权相同因而广度优先即为最短路
130. 被围绕的区域	中等	从边界反向遍历标记安全区，同属改变搜索起点的技巧