LeetCode——地图分析

NO.1162 地图分析中等

思路一：BFS BFS经常用来解决最短路径问题，但是本题用来求解最长路径问题也是可行的。

BFS求最短路径问题就是遇到第一个符合要求的节点就返回。

BFS求最长路径问题则是搜索完全部节点之后再返回。

对本题而言，先遍历将所有的陆地入队作为第0层，然后第0层出队放入第1层。。。广搜层序遍历。。。搜索结束时的层数就是陆地距离最远的海洋的距离。

用boolean数组标记网格的每个点是否入队过。或者”沉岛思想”直接在网格上进行标记，入过队的海洋(0)置为1(非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.size() == n * n || queue.isEmpty()) {
        return -1;
    }
    //BFS记录一下最后是第几层
    int round=-1;
    while (!queue.isEmpty()) {
        round++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] temp = queue.poll();
            //向下
            if (temp[0] + 1 < n && grid[temp[0] + 1][temp[1]] == 0) {
                grid[temp[0] + 1][temp[1]] = 1;//标记已入队
                queue.add(new int[]{temp[0] + 1, temp[1]});
            }
            //向右
            if (temp[1] + 1 < n && grid[temp[0]][temp[1]+1] == 0) {
                grid[temp[0]][temp[1]+1]=1;
                queue.add(new int[]{temp[0],temp[1]+1});
            }
            //向上
            if (temp[0] - 1 >= 0 && grid[temp[0]-1][temp[1]] == 0) {
                grid[temp[0]-1][temp[1]] =1;
                queue.add(new int[]{temp[0]-1,temp[1]});
            }
            //向左
            if (temp[1] - 1 >= 0 && grid[temp[0]][temp[1]-1] == 0) {
                grid[temp[0]][temp[1]-1]=1;
                queue.add(new int[]{temp[0],temp[1]-1});
            }
        }
    }
    return round;
}

时间复杂度：O(n^2) 遍历一遍grid。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.1162 地图分析 中等

NO.1162 地图分析中等