[LeetCode] 286. Walls and Gates

You are given an m x n grid rooms initialized with these three possible values.

-1 A wall or an obstacle.
0 A gate.
INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example 1:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Example 2:
Input: rooms = [[-1]]
Output: [[-1]]

Constraints:
m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] is -1, 0, or 231 - 1.

墙与门。

你被给定一个 m × n 的二维网格 rooms ，网格中有以下三种可能的初始化值：
-1 表示墙或是障碍物
0 表示一扇门
INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。
你要给每个空房间位上填上该房间到最近门的距离，如果无法到达门，则填 INF 即可。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/walls-and-gates
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

题意是给一个二维矩阵，里面的 -1 代表墙，0 代表门，INF 代表一个空的房间。请改写所有的 INF，表明每个 INF 到最近的门的距离。

这一题是带障碍物的 flood fill类的题目，既然是问最短距离，所以这个题目应该还是偏 BFS 做。还有一题思路比较接近的是 542 题，也是在矩阵内通过已知的一些距离去累加起来找未知坐标的距离。还有一道题也比较类似，也是带障碍物的 flood fill 类型的题目，1730 题。

具体思路是我们从矩阵中的门出发，也就是先找到矩阵中的 0，把这些 0 的坐标放入 queue。从 queue 中弹出这些 0 的时候，往四个方向扫描，看看这些 0 的周围是否有 INF。如果有，则这些 INF 就有一个具体的距离了，把这些有了距离的 INF 再放入 queue。这些 INF 有了具体的距离之后，别的距离门更远的 INF 也就可以被计算出具体的距离了。

复杂度

时间O(mn)
空间O(mn)

代码

Java实现

class Solution {
    int m;
    int n;
    int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public void wallsAndGates(int[][] rooms) {
        m = rooms.length;
        n = rooms[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    queue.offer(new int[] { i, j });
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] dir : dirs) {
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];
				// 在矩阵范围内且是一个房间
				// 注意房间的定义是Integer.MAX_VALUE
                if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] == Integer.MAX_VALUE) {
                    rooms[x][y] = rooms[cur[0]][cur[1]] + 1;
                    queue.offer(new int[] { x, y });
                }
            }
        }
    }
}

[LeetCode] 286. Walls and Gates

思路

复杂度

代码

相关题目