01 矩阵 图解题解

这道题到底在问什么

输入

mat = [[0,0,1],[0,1,1],[1,1,1]]

输出

[[0,0,1],[0,1,2],[1,2,3]]

解释

0 所在格距离是 0；右下角的 1 离最近的 0 要走 3 步。

最优解：一步一步想明白

1. 30=蓝 · 1=绿这是我们的例子：左上角连着三个 0（蓝色），其余都是 1（绿色）。目标是把每个 1 替换成「它离最近 0 有多远」。
2. 4每个 1 都去找最近的 0最直白的想法：对每一个 1，单独做一次广度优先搜索，从它出发往外扩，第一次碰到 0 时走过的步数就是答案。
3. 5从 (2,2) 出发往外扩比如右下角 (2,2) 这个 1（紫色）。把它当起点，向四周扩散，一圈圈搜，直到撞上一个 0 才停。
4. 6走 1 圈还没碰到 0从 (2,2) 往外扩第 1 圈，碰到 (1,2)、(2,1)（紫色），它们都还是 1，没撞到 0，得接着往外扩。
5. 7走 3 圈才碰到 0为了搞清楚这一个格子的答案，它要往外扩好几圈才碰到 0。每个 1 都这样来一遍，重复搜索的格子太多，太慢了。
6. 8重复劳动太多假设有 m×n 个 1，每个都从头搜一遍整张图，这就是平方级的重复劳动。格子稍多就会超时。我们需要换个思路。
7. 9不要从 1 出发，要从 0 出发反转一下：与其让每个 1 去找 0，不如让所有的 0 一起向外扩散。第一波碰到的 1 距离是 1，第二波是 2……谁先被碰到，谁的答案就先定下来。
8. 10BFS 第一次到达 = 最短广度优先搜索天然按距离一层层往外走：距离 1 的全走完，才走距离 2 的。所以一个格子第一次被碰到时记下的步数，一定就是它离最近 0 的最短距离，之后不用再改。
9. 11(0,0) 入队，距离=0开局把所有 0 入队、距离记 0。先看第一个 0 —— (0,0)，距离 0（紫色），放进队列。其余还没确定的格子先标成「·」。
10. 12(0,1) 入队，距离=0第二个 0 是 (0,1)，距离也是 0，一并入队。看队列又多了一个 d=0。
11. 13(1,0) 入队，距离=0最后一个 0 是 (1,0)，距离 0 入队。现在三个 0 全在队列里（距离都 0），这就是多源 BFS的「多源」——同时从它们起跑。
12. 14(0,1) 的右邻居 → 距离 1把第 0 层的 0 依次取出看邻居。(0,1) 右边的 (0,2) 第一次被碰到，距离 = 0 + 1 = 1（紫色波面），填进格子并入队。三个 0 变蓝表示已处理。
13. 15(0,1)/(1,0) 的邻居 → 距离 1中间的 (1,1) 被它上面的 0、左边的 0 一步碰到，距离记 1。(0,2) 这格答案已锁定变蓝。波面一格一格往里填。
14. 16(1,0) 的下邻居 → 距离 1(1,0) 下面的 (2,0) 也第一次被碰到，距离 1。至此距离 1 的一整圈都填好了：(0,2)、(1,1)、(2,0)，它们排队等下一轮往外扩。
15. 17这三格答案锁定 = 1距离 1 的三个格子全部锁定（蓝色=已确定），不会再改。每个 1 都是被离它最近的那个 0 一步碰到的——这正是多源同时扩散的好处。
16. 18距离 1 的邻居 → 距离 2现在轮到距离 1 的那一圈往外扩。(1,2) 被 (0,2) 或 (1,1) 碰到，第一次到达，距离 = 1 + 1 = 2（紫色波面），填上并入队。
17. 19距离 1 的邻居 → 距离 2(2,1) 被 (1,1) 或 (2,0) 碰到，距离也是 2。(1,2) 锁定变蓝。距离 2 的这圈填完了，只剩最角落的 (2,2) 还是「·」。
18. 20这两格答案锁定 = 2(1,2) 和 (2,1) 的距离锁定为 2。波面一圈圈往外推，只剩最角落的 (2,2) 还没确定。
19. 21距离 2 的邻居 → 距离 3距离 2 的格子往外扩，碰到最后的 (2,2)。它第一次被碰到，距离 = 2 + 1 = 3（紫色波面），填上。
20. 22队列空 → 结束队列空了，所有格子的距离都确定了：[[0,0,1],[0,1,2],[1,2,3]]。整张图只扫了一遍，每个格子只在第一次被碰到时写一次值。
21. 23距 0 一步的格子回看这道波是怎么漫开的。紫色高亮的是距离 1那一圈：(0,2)、(1,1)、(2,0)，紧贴着那片 0。
22. 24距 0 两步的格子再外一圈是距离 2：(1,2)、(2,1)。它们离那片 0 隔了一圈，所以是两步。
23. 25距 0 三步的格子最外圈只有最角落的 (2,2)，距离 3。整张图就是从左上那片 0 出发，像水波一样一圈圈漫开：1、2、3。每个格子的数字 = 这道波第几圈漫到它。
24. 26多次 BFS → 一次 BFS从「每个 1 单独搜全图」变成「所有 0 一起扩散、全图只走一遍」，复杂度从平方级降到线性级，这就是多源 BFS 的威力。
25. 27入队 → 出队扩散 → 标距离用 -1 标记「还没访问」非常好用：邻居只要还是 -1，就说明它第一次被碰到，写上距离并入队；已经不是 -1 的就跳过，绝不重复。
26. 30记住这一句多源 BFS 的本质：把所有起点想象成连到一个「超级源点」，从它出发的一次普通 BFS，就同时算出了到「最近任意一个起点」的距离。
27. 32从单个 1 出发 = 重复劳动如果坚持从每个 1（红色）出发各搜一遍，(1,1)、(1,2)、(2,2) 的搜索范围会大量重叠，同一片区域被反复走，这就是慢的根源。

⚠️ 容易写错的地方

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

from collections import deque
class Solution:
    def updateMatrix(self, mat):
        m, n = len(mat), len(mat[0])
        dist = [[-1] * n for _ in range(m)]
        q = deque()
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dist[i][j] = 0
                    q.append((i, j))
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while q:
            i, j = q.popleft()
            for di, dj in dirs:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and dist[ni][nj] == -1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni, nj))
        return dist

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, -1));
        queue<pair<int,int>> q;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.empty()) {
            pair<int,int> cur = q.front(); q.pop();
            int i = cur.first, j = cur.second;
            for (int k = 0; k < 4; k++) {
                int ni = i + dirs[k][0], nj = j + dirs[k][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && dist[ni][nj] == -1) {
                    dist[ni][nj] = dist[i][j] + 1;
                    q.push({ni, nj});
                }
            }
        }
        return dist;
    }
};

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        ArrayDeque<int[]> q = new ArrayDeque<int[]>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.offer(new int[]{i, j});
                } else {
                    dist[i][j] = -1;
                }
            }
        }
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int i = cur[0], j = cur[1];
            for (int k = 0; k < 4; k++) {
                int ni = i + dirs[k][0], nj = j + dirs[k][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && dist[ni][nj] == -1) {
                    dist[ni][nj] = dist[i][j] + 1;
                    q.offer(new int[]{ni, nj});
                }
            }
        }
        return dist;
    }
}

复杂度

面试官可能追问