你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。

我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。

如果我们的地图上只有陆地或者海洋，请返回 -1。

 

示例 1：

1 0 1
0 0 0
1 0 1 
1
2
3
4
输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大，最大距离为 2。

示例 2：

1 0 0
0 0 0
0 0 0 
1
2
3
4
输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释： 
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大，最大距离为 4。

 
提示：

  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[i][j] 不是 0 就是 1
参考解答
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
  var lands = [];
  var rows = grid.length;
  var cols = grid[0].length;
  var res = -1;

  // 找出所有的陆地的坐标
  for (var i = 0; i < rows; i++) {
    for (var j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        lands.push([i, j]);
      }
    }
  }

  // 全是陆地或海洋
  if (!lands.length || lands.length === rows * cols) return -1; 
  // 遍历所有陆地
  while (lands.length > 0) {
    var len = lands.length;
    while (len > 0) {
      len--;
      var land = lands.shift(); // 删掉第一元素
      // 向4个方向搜索
      // 上、右、下、左
      var ways = [ [-1, 0], [0, 1], [1, 0], [0, -1] ];
      for (var i = 0; i < 4; i++) {
        var row = land[0] + ways[i][0]; // row 方向
        var col = land[1] + ways[i][1]; // col 方向
        // 判断是否越界
        if (
          row < 0 ||
          row >= rows ||
          col < 0 ||
          col >= cols ||
          (grid[row] && grid[row][col] === 1)
        ) {
          continue;
        }

        // 找到海洋
        if (grid[row] && grid[row][col] === 0) {
          lands.push([ row, col ]);
          grid[row][col] = 1;
        }
      }
    }
    res++;
  }

  return res;
};

解题思路

广度优先搜索。