墙与门 图解题解

这道题到底在问什么

最优解：一步一步想明白

1. 3别一个房间一个房间去搜门。反过来：从所有门一起出发，像水波一样一圈圈往外漫。空房间第一次被波纹碰到，那一刻的层数就是它到最近门的最短距离。
2. 4门=源点(2个)，墙=障碍(3个)，空房间=∞(11个)把全部 2 个门 (3,0)、(3,3) 一次性放进队列，它们都算「第 0 层」。墙 (0,1)、(2,1)、(2,3) 是灰色障碍，水波绕着走。11 个 ∞ 空房间等着被波纹碰到。
3. 5当前层=1，来路=(3,0)波纹从已知格 (3,0) 往邻居 (2,0) 漫一步。这是空房间 (2,0) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 1，以后不再更新。
4. 6已填 1 个空房间给 (2,0) 填上 1，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
5. 7当前层=1，来路=(3,0)波纹从已知格 (3,0) 往邻居 (3,1) 漫一步。这是空房间 (3,1) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 1，以后不再更新。
6. 8已填 2 个空房间给 (3,1) 填上 1，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
7. 9当前层=1，来路=(3,3)波纹从已知格 (3,3) 往邻居 (3,2) 漫一步。这是空房间 (3,2) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 1，以后不再更新。
8. 10已填 3 个空房间给 (3,2) 填上 1，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
9. 11当前层=2，来路=(2,0)波纹从已知格 (2,0) 往邻居 (1,0) 漫一步。这是空房间 (1,0) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 2，以后不再更新。
10. 12已填 4 个空房间给 (1,0) 填上 2，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
11. 13当前层=2，来路=(3,2)波纹从已知格 (3,2) 往邻居 (2,2) 漫一步。这是空房间 (2,2) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 2，以后不再更新。
12. 14已填 5 个空房间给 (2,2) 填上 2，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
13. 15当前层=3，来路=(1,0)波纹从已知格 (1,0) 往邻居 (0,0) 漫一步。这是空房间 (0,0) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 3，以后不再更新。
14. 16已填 6 个空房间给 (0,0) 填上 3，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
15. 17当前层=3，来路=(1,0)波纹从已知格 (1,0) 往邻居 (1,1) 漫一步。这是空房间 (1,1) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 3，以后不再更新。
16. 18已填 7 个空房间给 (1,1) 填上 3，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
17. 19当前层=3，来路=(2,2)波纹从已知格 (2,2) 往邻居 (1,2) 漫一步。这是空房间 (1,2) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 3，以后不再更新。
18. 20已填 8 个空房间给 (1,2) 填上 3，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
19. 21当前层=4，来路=(1,2)波纹从已知格 (1,2) 往邻居 (0,2) 漫一步。这是空房间 (0,2) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 4，以后不再更新。
20. 22已填 9 个空房间给 (0,2) 填上 4，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
21. 23当前层=4，来路=(1,2)波纹从已知格 (1,2) 往邻居 (1,3) 漫一步。这是空房间 (1,3) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 4，以后不再更新。
22. 24已填 10 个空房间给 (1,3) 填上 4，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
23. 25当前层=5，来路=(0,2)波纹从已知格 (0,2) 往邻居 (0,3) 漫一步。这是空房间 (0,3) 第一次被碰到 —— 第一次碰到就是最近的门，所以它的距离就定死为 5，以后不再更新。
24. 26已填 11 个空房间给 (0,3) 填上 5，它也加进队列尾，下一圈轮到它再往外漫一步。队列严格按层推进，所以填进去的永远是最短距离。
25. 27全部 11 个空房间已填，最大距离=5队列空了，水波漫遍所有能到的房间。每个 ∞ 都换成了到最近门的最短步数。要是某个房间被墙完全围死、波纹到不了，它就一直留着 ∞（本例没有这种死角）。

完整代码（Python / C++ / Java）

def wallsAndGates(rooms):
    if not rooms: return
    R, C = len(rooms), len(rooms[0])
    from collections import deque
    q = deque((i, j) for i in range(R)
            for j in range(C) if rooms[i][j] == 0)
    while q:
        i, j = q.popleft()
        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < R and 0 <= nj < C \
                    and rooms[ni][nj] == 2147483647:
                rooms[ni][nj] = rooms[i][j] + 1
                q.append((ni, nj))

void wallsAndGates(vector<vector<int>>& rooms){
    if(rooms.empty()) return;
    int R = rooms.size(), C = rooms[0].size();
    queue<pair<int,int>> q;
    for(int i=0;i<R;i++) for(int j=0;j<C;j++)
        if(rooms[i][j]==0) q.push({i,j});
    int dir[5]={-1,0,1,0,-1};
    while(!q.empty()){
        auto [i,j] = q.front(); q.pop();
        for(int d=0;d<4;d++){
            int ni=i+dir[d], nj=j+dir[d+1];
            if(ni<0||nj<0||ni>=R||nj>=C) continue;
            if(rooms[ni][nj]!=INT_MAX) continue;
            rooms[ni][nj]=rooms[i][j]+1; q.push({ni,nj});
        }
    }
}

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0) return;
        int R = rooms.length, C = rooms[0].length;
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (rooms[i][j] == 0) q.add(new int[]{i, j});
        int[] dir = {-1, 0, 1, 0, -1};
        while (!q.isEmpty()) {
            int[] c = q.poll();
            for (int d = 0; d < 4; d++) {
                int ni = c[0] + dir[d], nj = c[1] + dir[d + 1];
                if (ni < 0 || nj < 0 || ni >= R || nj >= C) continue;
                if (rooms[ni][nj] != Integer.MAX_VALUE) continue;
                rooms[ni][nj] = rooms[c[0]][c[1]] + 1;
                q.add(new int[]{ni, nj});
            }
        }
    }
}

复杂度

面试官可能追问