LC.P1162[地图分析]

方法一：BFS(超时)

对每个海洋位置做一次 BFS：求得每个海洋的最近陆地距离，然后在所有的距离中取 $max$作为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    int n;
    int[][] grid;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int maxDistance(int[][] grid) {
        this.grid = grid;
        n = grid.length;
        int ans = -1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    ans = Math.max(ans, bfs(i, j));
                }
            }
        }
        return ans;
    }

    private int bfs(int i, int j) {
        Deque<int[]> queue = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        queue.offer(new int[]{i, j});
        map.put(i * n + j, 0);
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            int step = map.get(x * n + y);
            if (grid[x][y] == 1) return step;
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                int key = nx * n + ny;
                if (map.containsKey(key)) continue;
                queue.offer(new int[]{nx, ny});
                map.put(key, step + 1);
            }
        }
        return -1;
    }
}
  • 时间复杂度：$O(n^4)$
  • 空间复杂度：$O(n^2)$

方法二：多源BFS

多源最短路问题：求从多个源点到达一个/多个汇点的最短路径。

从每个陆地区域出发，多个陆地区域每次同时向往扩散一圈，每个海洋区域被首次覆盖时所对应的圈数，就是海洋区域距离最近的陆地区域的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int maxDistance(int[][] grid) {
        int n = grid.length;
        Deque<int[]> queue = new ArrayDeque<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    map.put(i * n + j, 0);
                }
            }
        }
        int ans = -1;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            int step = map.get(x * n + y);
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 越界
                if (grid[nx][ny] != 0) continue; // 已经访问过
                queue.offer(new int[]{nx, ny});
                grid[nx][ny] = step + 1;
                map.put(nx * n + ny, step + 1);
                ans = Math.max(ans, step + 1);
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

方法三：优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int maxDistance(int[][] grid) {
        int n = grid.length;
        Deque<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    grid[i][j] = -1;
                }
            }
        }
        int ans = -1;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            int step = Math.max(grid[x][y], 0);
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // 越界
                if (grid[nx][ny] != 0) continue; // 已经访问过
                queue.offer(new int[]{nx, ny});
                grid[nx][ny] = step + 1;
                ans = Math.max(ans, step + 1);
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$