墙与门 图解题解

这道题到底在问什么

示例

INF/门/墙矩阵 → 每格最近门距离

最优解：一步一步想明白

1. 3从每个空房间找最近门，会重复搜索。
2. 4把所有门同时入队，多源 BFS 一层层扩散，第一次到达就是最短距离。
3. 5多源 BFS：把所有门(0)同时入队，距离 0。墙(-1，灰)不可走，空房间(∞)待填。本例有左上、右下两个门。
4. 6两个门同时向四周扩一圈：相邻空房间填 1(距最近门 1 步)。
5. 7再外扩一圈：(0,2)、(2,0) 填 2。墙 -1 自动绕过、已填的格不再重复。
6. 8关键帧：所有门同时向外扩散，每个房间第一次被触到时的层数 = 到最近门的距离。这就是多源 BFS 比「逐房间各自找门」快的原因。
7. 11一句话记住：把所有门同时入队，多源 BFS 一层层扩散，第一次到达就是最短距离。
8. 20这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=graph 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。

⚠️ 容易写错的地方

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

class Solution:
    def wallsAndGates(self, rooms):
        from collections import deque
        rows, cols = len(rooms), len(rooms[0])
        q = deque((r, c) for r in range(rows) for c in range(cols) if rooms[r][c] == 0)
        while q:
            r, c = q.popleft()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == 2147483647:
                    rooms[nr][nc] = rooms[r][c] + 1
                    q.append((nr, nc))

class Solution {
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        int m = rooms.size(), n = rooms[0].size();
        queue<pair<int,int>> q;
        for (int r=0;r<m;r++) for (int c=0;c<n;c++) if (rooms[r][c] == 0) q.push({r,c});
        int d[5] = {1,0,-1,0,1};
        while (!q.empty()) {
            auto [r,c] = q.front(); q.pop();
            for (int k=0;k<4;k++) {
                int nr=r+d[k], nc=c+d[k+1];
                if (nr>=0&&nr<m&&nc>=0&&nc<n&&rooms[nr][nc]==INT_MAX) {
                    rooms[nr][nc] = rooms[r][c] + 1;
                    q.push({nr,nc});
                }
            }
        }
    }
};

class Solution {
    public void wallsAndGates(int[][] rooms) {
        int m=rooms.length,n=rooms[0].length;
        Queue<int[]> q = new ArrayDeque<>();
        for(int r=0;r<m;r++) for(int c=0;c<n;c++) if(rooms[r][c]==0) q.offer(new int[]{r,c});
        int[] d={1,0,-1,0,1};
        while(!q.isEmpty()){
            int[] cur=q.poll();
            for(int k=0;k<4;k++){
                int nr=cur[0]+d[k], nc=cur[1]+d[k+1];
                if(nr>=0&&nr<m&&nc>=0&&nc<n&&rooms[nr][nc]==Integer.MAX_VALUE){
                    rooms[nr][nc]=rooms[cur[0]][cur[1]]+1;
                    q.offer(new int[]{nr,nc});
                }
            }
        }
    }
}

# 多源 BFS 骨架
q = deque(所有门的坐标)        # 所有源同时入队，距离 0
while q:
    r, c = q.popleft()
    for 四个方向 nr, nc:
        if 在界内 and rooms[nr][nc]==∞:   # 只填未访问的空房间
            rooms[nr][nc] = rooms[r][c] + 1
            q.append((nr, nc))

复杂度

面试官可能追问