LeetCode 286. 墙与门

2023-10-28 HGNULB 约 6 分钟

文章信息 7 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决会员题 1-2 字节

题目描述

✅ 286. 墙与门

题意分析

网格中的 -1 表示墙，0 表示门，INF 表示空房间。要求原地把每个空房间改为到最近门的最短步数，只能上下左右移动，不能穿墙；无法到达任何门的房间继续保持 INF。

四向路径可以反过来走，所以从房间找最近门，等价于从所有门向外寻找房间。把所有门同时作为起点，就能在一次搜索中计算整张图的最近距离。

解法：多源 BFS

核心思路

[!blue]

先扫描网格，把全部门加入队列。它们的距离都是 0，属于 BFS 的同一初始层。每次取出一个距离已经确定的格子，检查它的四个相邻位置。

邻居只有仍为 INF 时才需要处理：墙不能通过，门的距离已经是 0，其他有限值表示这个房间已经被发现。对未访问的空房间，写入 当前格子的距离 + 1，再将它加入队列。赋值既记录距离，也替代单独的访问标记。

所有移动的代价都是一步，FIFO 队列会先处理较小距离，再处理较大距离。若某个房间第一次被赋值为 d，更短的路径本应从更早处理的层到达它；既然没有更早发现，d 就已经是到全部门的最短距离，不需要再更新。

入队前立即赋值，让同层多个来源不会重复加入同一个房间。队列耗尽后，所有能从门到达的房间都已填好距离；被墙隔开的房间从未入队，自然保持 INF。如果没有门，初始队列为空，网格也会原样保留。

解题步骤

处理空网格，取得行列数，扫描并将所有值为 0 的门加入队列。

依次出队一个格子，枚举四个相邻坐标。

先检查是否越界，再判断邻居是否仍为 INF；任一条件不满足就跳过。

给未访问房间写入当前距离加一，随后入队。

直到队列为空。结果已经写在输入矩阵中，无需另建距离数组或处理不可达格子。

代码实现

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length;

        if (m == 0) {
            return;
        }

        int n = rooms[0].length;

        // 先将全部门作为零距离源点入队。
        Queue<int[]> queue = new ArrayDeque<>();

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (rooms[r][c] == 0) {
                    queue.offer(new int[] {
                        r,
                        c
                    });
                }
            }
        }

        int[] dr = new int[] {
            1,
            -1,
            0,
            0
        };
        int[] dc = new int[] {
            0,
            0,
            1,
            -1
        };
        int INF = 2147483647;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];

            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];

                if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
                    continue;
                }

                if (rooms[nr][nc] != INF) {
                    continue;
                }

                // 入队前立即写入距离，同时标记房间已被最短路径到达。
                rooms[nr][nc] = rooms[r][c] + 1;
                queue.offer(new int[] {
                    nr,
                    nc
                });
            }
        }
    }
}

func wallsAndGates(rooms [][]int) {
    m := len(rooms)
    if m == 0 {
        return
    }
    n := len(rooms[0])
    type pair struct{ r, c int }

    // 先将全部门作为零距离源点入队。
    queue := make([]pair, 0)
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if rooms[r][c] == 0 {
                queue = append(queue, pair{r: r, c: c})
            }
        }
    }

    dr := []int{
        1,
        -1,
        0,
        0,
    }
    dc := []int{
        0,
        0,
        1,
        -1,
    }
    const INF = 2147483647

    head := 0
    for head < len(queue) {
        cur := queue[head]
        head++
        for k := 0; k < 4; k++ {
            nr := cur.r + dr[k]
            nc := cur.c + dc[k]
            if nr < 0 || nr >= m || nc < 0 || nc >= n {
                continue
            }
            if rooms[nr][nc] != INF {
                continue
            }
            // 入队前立即写入距离，同时标记房间已被最短路径到达。
            rooms[nr][nc] = rooms[cur.r][cur.c] + 1
            queue = append(queue, pair{r: nr, c: nc})
        }
    }
}

复杂度分析

设网格有 m 行、n 列。

时间复杂度：$O(mn)$。先扫描所有格子，每个门或可达房间至多入队一次，每次只检查四个方向。

空间复杂度：$O(mn)$，队列最坏可保存线性于格子总数的位置；距离和访问状态直接写入输入矩阵。

关键点总结

[!green]

所有门同时处在距离 0 的初始层，才能比较各个门到房间的最短路径。

等代价移动配合 FIFO 顺序，保证首次发现的距离就是最终最短距离。

只处理 INF，赋值同时完成访问标记，不可达房间自然保留原值。

易错点总结

[!yellow]

只把一扇门作为起点：得到的只是到这一扇门的距离，可能错过其他更近的门。

只排除墙，不排除已赋值格子：会反复搜索，甚至覆盖已经确定的最短距离。

出队时才赋值：同一房间可能在出队前被多个邻居重复加入，应在入队前写入距离。

先读取邻居再检查坐标：网格边缘的相邻位置可能越界。

把不可达房间改成 0：0 表示门，不可达应继续保留 INF。

相似题目

题目	难度	关联与区别
542. 01 矩阵	中等	同样从所有目标格同时开始BFS，计算每个位置到最近目标的距离。
994. 腐烂的橘子	中等	同样按层扩散，原题多个腐烂源同时传播，本题门是多个距离为0的源。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2023/85922154

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！