[1162] 地图分析

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例 1：

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]

输出：2

解释：

海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

示例 2：

输入：grid = [[1,0,0],[0,0,0],[0,0,0]]

输出：4

解释：

海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

提示：

n == grid.length

n == grid[i].length

1 <= n <= 100

grid[i][j] 不是 0 就是 1

这道题有一点像 FloodFill 问题，遍历每一个海洋点，通过方向去寻找岛屿。

而同时，它又是一道求图最短距离的问题，因此需要使用到 BFS 去做查找。

根据专题中对这两类题的了解，我们可以写出如下解法：

通过遍历每一个海洋节点，再通过 BFS 方向遍历找到离海洋最近的陆地节点，算出每一个海洋节点的最近距离，取最大值返回。

function maxDistance(grid: number[][]): number {
  const height = grid.length;
  const width = grid[0].length;
  const direction = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1]
  ];

  let res: number = -1;
  for (let i = 0; i < height; i++) {
    for (let j = 0; j < width; j++) {
      if (grid[i][j] === 0) {
        const distance = bfs(i, j);
        res = Math.max(distance, res);
      }
    }
  }
  return res;

  function bfs(row: number, col: number) {
    const visited: boolean[][] = Array(height)
      .fill(0)
      .map(x => Array(width).fill(false));

    const queue: [row: number, col: number][] = [];
    queue.unshift([row, col]);
    visited[row][col] = true;

    while (queue.length > 0) {
      const [currRow, currCol] = queue.pop();
      for (let [a, b] of direction) {
        const x: number = currRow + a;
        const y: number = currCol + b;

        // 越界或已访问过，跳过
        if (x < 0 || x >= height || y < 0 || y >= width) {
          continue;
        }
        if (visited[x][y]) continue;

        // 当第一次搜索到陆地，此时一定为最近陆地，返回距离
        if (grid[x][y] === 1) {
          return Math.abs(x - row) + Math.abs(y - col);
        }

        // 入队并记录
        queue.unshift([x, y]);
        visited[x][y] = true;
      }
    }
    return -1;
  }
}

而这样写从代码上看就十分复杂，而且直接提交的话有可能会提示超时。

接下来我们分析一下复杂度。发现最坏时间复杂度居然达到了 O(n^(2*2)) = O(n^4) 的程度。这显然有点复杂了。

而换一个角度想想，如果我们不从海洋的角度出发，而是从陆地的角度出发呢？

我们找到每一个陆地节点，并同时对陆地节点进行BFS扩散，当第一次经过某个海洋节点，就标记一次距离最近陆地的距离。

实际上，这就是多源 BFS。一个同时从多点进行BFS扩散，帮助我们缩短找到目标节点的时间和复杂度的方式。

而显然，最后访问到的海洋节点，则一定是离陆地最远的海洋。返回最大的标记距离即可。

function maxDistance(grid: number[][]): number {
  const height = grid.length;
  const width = grid[0].length;
  const direction = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1]
  ];

  let res: number = -1;

  // 将所有陆地节点入队
  const queue: [row: number, col: number][] = [];
  for (let i = 0; i < height; i++) {
    for (let j = 0; j < width; j++) {
      if (grid[i][j] === 1) {
        queue.push([i, j]);
      }
    }
  }

  // 没有陆地或者没有海洋
  if (queue.length === 0 || queue.length === height * width) {
    return -1;
  }

  // 多源 BFS，从所有岛屿开始向外 BFS
  while (queue.length > 0) {
    const [x, y] = queue.pop();

    for (let [a, b] of direction) {
      const newX = x + a;
      const newY = y + b;

      // 越界，跳过
      if (newX < 0 || newX >= height || newY < 0 || newY >= width) {
        continue;
      }

      // 当前节点为陆地，或是已经被遍历过，跳过
      if (grid[newX][newY] !== 0) {
        continue;
      }

      // 新的海洋，距离为上一层 BFS 的节点距离 + 1
      const distance = grid[x][y] + 1;
      grid[newX][newY] = distance;
      res = Math.max(res, distance);

      queue.unshift([newX, newY]);
    }
  }

  // 由于距离从陆地的1开始记录，而显然陆地距离自己为0，因此结果要去掉
  return res - 1;
}