地图分析 图解题解

这道题到底在问什么

输入

grid = [[1,0,1],[0,0,0],[1,0,1]]

输出

2

解释

四个角是陆地，正中间 (1,1) 这片海离最近陆地 2 步，是最远的。

最优解：一步一步想明白

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

⚠️ 容易写错的地方

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

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

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dist(n, vector<int>(n, -1));
        queue<pair<int,int>> q;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
        if (q.empty() || (int)q.size() == n * n) return -1;
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        int ans = 0;
        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 < n && nj >= 0 && nj < n && dist[ni][nj] == -1) {
                    dist[ni][nj] = dist[i][j] + 1;
                    ans = max(ans, dist[ni][nj]);
                    q.push({ni, nj});
                }
            }
        }
        return ans;
    }
};

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        int[][] dist = new int[n][n];
        ArrayDeque<int[]> q = new ArrayDeque<int[]>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    q.offer(new int[]{i, j});
                } else {
                    dist[i][j] = -1;
                }
            }
        }
        if (q.isEmpty() || q.size() == n * n) return -1;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int ans = 0;
        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 < n && nj >= 0 && nj < n && dist[ni][nj] == -1) {
                    dist[ni][nj] = dist[i][j] + 1;
                    ans = Math.max(ans, dist[ni][nj]);
                    q.offer(new int[]{ni, nj});
                }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问