1162：网格结构 BFS 遍历

1162 地图分析：离开陆地的最远距离（Medium）

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
如果网格上只有陆地或者海洋，请返回 -1。

为了避免重复遍历，这里使用到了和 DFS 遍历一样的技巧：把已遍历的格子标记为 2。注意：我们在将格子放入队列之前就将其标记为 2。=
在将格子放入队列之前就检查其坐标是否在网格范围内，避免将「不存在」的格子放入队列。

网格BFS层序遍历

// 网格结构的层序遍历
// 从格子 (i, j) 开始遍历
void bfs(int[][] grid, int i, int j) {Queue<int[]> queue = new ArrayDeque<>();queue.add(new int[]{r, c});while (!queue.isEmpty()) {int n = queue.size();for (int i = 0; i < n; i++) { int[] node = queue.poll();int r = node[0];int c = node[1];if (r-1 >= 0 && grid[r-1][c] == 0) {grid[r-1][c] = 2;queue.add(new int[]{r-1, c});}if (r+1 < N && grid[r+1][c] == 0) {grid[r+1][c] = 2;queue.add(new int[]{r+1, c});}if (c-1 >= 0 && grid[r][c-1] == 0) {grid[r][c-1] = 2;queue.add(new int[]{r, c-1});}if (c+1 < N && grid[r][c+1] == 0) {grid[r][c+1] = 2;queue.add(new int[]{r, c+1});}}}
}

由于一个格子有四个相邻的格子，代码中判断了四遍格子坐标的合法性，代码稍微有点啰嗦。我们可以用一个 moves 数组存储相邻格子的四个方向：

int[][] moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1},
};

然后把四个 if 判断变成一个循环：

for (int[][] move : moves) {int r2 = r + move[0];int c2 = c + move[1];if (inArea(grid, r2, c2) && grid[r2][c2] == 0) {grid[r2][c2] = 2;queue.add(new int[]{r2, c2});}
}

1162题

假设网格中只有一个陆地格子，我们可以从这个陆地格子出发做层序遍历，直到所有格子都遍历完。最终遍历了几层，海洋格子的最远距离就是几。
那么有多个陆地格子的时候怎么办呢？一种方法是将每个陆地格子都作为起点做一次层序遍历，但是这样的时间开销太大。
BFS 完全可以以多个格子同时作为起点。我们可以把所有的陆地格子同时放入初始队列，然后开始层序遍历。这种遍历方法实际上叫做「多源 BFS」
在代码中，我们不需要给每个遍历到的格子标记层数，只需要用一个 distance 变量记录当前的遍历的层数（也就是到陆地格子的距离）即可。

public int maxDistance(int[][] grid) {int N = grid.length;Queue<int[]> queue = new ArrayDeque<>();// 将所有的陆地格子加入队列for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (grid[i][j] == 1) {queue.add(new int[]{i, j});}}}// 如果地图上只有陆地或者海洋，返回 -1if (queue.isEmpty() || queue.size() == N * N) {return -1;}int[][] moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1},};int distance = -1; // 记录当前遍历的层数（距离）while (!queue.isEmpty()) {distance++;int n = queue.size();for (int i = 0; i < n; i++) { int[] node = queue.poll();int r = node[0];int c = node[1];for (int[] move : moves) {int r2 = r + move[0];int c2 = c + move[1];if (inArea(grid, r2, c2) && grid[r2][c2] == 0) {grid[r2][c2] = 2;queue.add(new int[]{r2, c2});}}}}return distance;
}// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}