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;
}