LeetCode.1162.As Far from Land as Possible 离所有陆地最远的海洋/地图分析

题目描述

1162 As Far from Land as Possible
https://leetcode-cn.com/problems/as-far-from-land-as-possible/

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: [
[1,0,1],
[0,0,0],
[1,0,1]]
Output: 2
Explanation:
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [
[1,0,0],
[0,0,0],
[0,0,0]]
Output: 4
Explanation:
The cell (2, 2) is as far as possible from all the land with distance 4.

Note:
1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1

---

解题过程

相似题目
LeetCode.994.Rotting Oranges 腐烂的橘子
LeetCode.1162.As Far from Land as Possible 离所有陆地最远的海洋/地图分析
LeetCode.542.01 Matrix 01矩阵

广度优先搜索BFS

一开始用的最直接的方法，每找到一个海洋(grid[i][j] == 0)就开始一次bfs，找到其最近的陆地并记录下此距离，然后在这些距离里面取一个最大值。
但是有一个超大的测试用例一直过不去，总是超时。
时间复杂度 O(n^4)，空间复杂度 O(n^2)

private static class SolutionV2020 {
  int[] dx = {-1, 0, 1, 0};
  int[] dy = {0, 1, 0, -1};

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

  // 从 x,y 开始一次bfs，返回到最近陆地的距离
  private int bfs(int[][] grid, int x, int y) {
      // 记录 (x,y) 是否已访问过，防止回退
      Set<Pair<Integer, Integer>> visited = new HashSet<>();

      Deque<Pair<Integer, Integer>> queue = new LinkedList<>();
      queue.offer(new Pair<>(x, y));
      visited.add(new Pair<>(x, y));

      while (!queue.isEmpty()) {
          Pair<Integer, Integer> pair = queue.poll();
          // 上下左右
          for (int i = 0; i < 4; i++) {
              int xx = pair.getKey() + dx[i], yy = pair.getValue() + dy[i];
              Pair<Integer, Integer> newPair = new Pair<>(xx, yy);
              if (xx >= 0 && xx < grid.length && yy >= 0 && yy < grid[0].length && !visited.contains(newPair)) {
                  if (grid[xx][yy] == 1) {
                      return Math.abs(xx - x) + Math.abs(yy - y);
                  } else {
                      visited.add(newPair);
                      queue.offer(new Pair<>(xx, yy));
                  }
              }
          }
      }
      return -1;
  }
}

多源广度优先搜索

从所有陆地结点开始一圈一圈向外扩散，直到遍历所有的海洋，则此时扩散的步骤就是距离陆地最远的海洋到陆地的距离。
扩散过程中，每扩散一圈，把对应的海洋结点打上标记。
时间复杂度 O(n^2)，空间复杂度 O(1)

private static class SolutionV2020 {
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};

    public int maxDistance(int[][] grid) {
        Deque<Pair<Integer, Integer>> queue = new LinkedList<>();
        // 所有陆地加入队列
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new Pair<>(i, j));
                }
            }
        }
        // 全是陆地或全是海洋
        if (queue.size() == grid.length * grid.length || queue.isEmpty()) {
            return -1;
        }

        // 从所有陆地结点开始一圈一圈向外扩散，step 是扩散的步骤
        int step = 0;
        while (!queue.isEmpty()) {
            // 取出下一层的所有海洋结点
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Pair<Integer, Integer> pair = queue.poll();
                // 找上下左右的海洋结点
                for (int k = 0; k < 4; k++) {
                    int xx = pair.getKey() + dx[k], yy = pair.getValue() + dy[k];
                    if (xx >= 0 && xx < grid.length && yy >= 0 && yy < grid[0].length && grid[xx][yy] == 0) {
                        // 结点值设为当前的层数(所有陆地结点视为第1层)
                        grid[xx][yy] = step + 2;
                        queue.offer(new Pair<>(xx, yy));
                    }
                }
            }
            step++;
        }
        return step - 1;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_1162_AsFarFromLandAsPossible.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1162_AsFarFromLandAsPossible.java

---