leedcode:地图分析

3.29日：地图分析

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

我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。如果我们的地图上只有陆地或者海洋，请返回 -1。

可以通过下图理解单源和多源广度优先搜索

分析：这道题很明显要用BFS（广度优先遍历）算法，实际上是求海洋格子到陆地格子的最长距离。

1、一开始，找出所有陆地格子，放入队列中，作为第0层的节点

2、然后进行BFS遍历，每个节点的相邻节点可能是上、下、左、右四个方向的节点

3、当遍历结束，当前的遍历层数就是海洋格子到陆地格子的最长距离

注意：为了在遍历中不重复访问海洋格子，我们将已经遍历过的海洋格子的值改为 2，和原来海洋格子里的 0 区别开来。

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});}}}// 如果我们的地图上只有陆地或者海洋，请返回 -1。if (queue.isEmpty() || queue.size() == N * N) {
    return -1;}int distance = -1;while (!queue.isEmpty()) {
    distance++;int n = queue.size();// 这里一口气取出 n 个结点，以实现层序遍历for (int i = 0; i < n; i++) {
    int[] cell = queue.poll();int r = cell[0];int c = cell[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});}}}return distance;
}