迷宫题库

墙与门

你被给定一个 m × n 的二维网格 rooms ，网格中有以下三种可能的初始化值：

-1 表示墙或是障碍物
0 表示一扇门
INF 无限表示一个空的房间。然后，我们用 231 - 1 = 2147483647 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。

你要给每个空房间位上填上该房间到最近门的距离，如果无法到达门，则填 INF 即可。

示例1:

输入：rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
输出：[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

方案A 广度优先搜索

思路: 从门开始做广度优先搜索。由于广度优先搜索保证我们在搜索 d + 1 距离的位置时，距离为 d 的位置都已经被搜索过了，所以到达每一个房间的时候都一定是最短距离。

:::details 点击查看代码

const directions=[[1,0],[-1,0],[0,1],[0,-1]];
function vallsAndGates(rooms){
    let m=rooms.length;
    if(m==0){
        return;
    }
    let n=rooms[0].length;
    let queue=[];
    for(let row=0;row<m;row++){
        for(let col=0;col<n;col++){
            if(rooms[row][col]==0){
                queue.push([row,col]);
            }
        }
    }
    while(queue.length){
        let point=queue.shift();
        let row=point[0];
        let col=point[1];
        for(let i=0;i<directions.length;i++){
            let r=row+directions[i][0];
            let c=col+directions[i][1];
            if(r<0||c<0||r>=m||c>=n||rooms[r][c]!=2147483647){
                continue;
            }
            rooms[r][c]=rooms[row][col]+1;
            queue.push([r,c]);
        }
    }
}

:::

性能分析:

时间复杂度： O(mn) 。

如果你对直接得到时间复杂度有困难的话，我们可以从简单的情况开始。

我们首先考虑只有一个门的情况，宽度优先搜索最多只需要 m×n 步就能到达所有的房间，所以时间复杂度是 O(mn) 。但是如果从 k 个门开始呢？

一旦我们到达了一个房间，并记录下它的距离时，这意味着我们也标记了这个房间已经被访问过了，这意味着每个房间最多会被访问一次。因此，时间复杂度与门的数量无关，所以时间复杂度为 O(mn) 。

空间复杂度： O(mn) 。

空间复杂度与队列的大小有关。我们最多将 m×n 个位置插入队列，所以空间最大为 m×n 。

墙与门​

方案A 广度优先搜索​

墙与门

方案A 广度优先搜索