Leetcode --- 岛屿问题（DFS求解）

写在前：参考这里

类比二叉树，网格进行DFS的两个要素：

• 访问相邻节点：对于格子 (r, c) 来说（r 和 c 分别代表行坐标和列坐标），四个相邻的格子分别是 (r-1, c)、(r+1, c)、(r, c-1)、(r, c+1)

• base case：超出网格的范围，即先污染后治理原则，发现错误撤出。

网格 DFS 遍历的框架代码：

void dfs(int[][] grid, int r, int c) {
    // 判断 base case
    if (!inArea(grid, r, c)) {
        return;
    }
    // 如果这个格子不是岛屿，直接返回
    if (grid[r][c] != 1) {
        return;
    }
    grid[r][c] = 2; // 将格子标记为「已遍历过」,避免重复遍历
    
    // 访问上、下、左、右四个相邻结点
    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
            && 0 <= c && c < grid[0].length;
}

1.岛屿数量（200 - 易）

题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 :

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

思路：DFS搜索，套模板。

代码实现：

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0 || (grid.length == 1 && grid[0].length == 0)) {
        return 0;
    }
    int M = grid.length, N = grid[0].length;
    int ans = 0;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == '1') {
                ans++;
                dfs(grid, i, j);
            }
        }
    }
    return ans;
}

private void dfs(char[][] grid, int r, int c) {
    if (!inArea(grid, r, c) || grid[r][c] != '1') return;
    grid[r][c] = '2'; // 标记为已遍历

    dfs(grid, r - 1, c);
    dfs(grid, r + 1, c);
    dfs(grid, r, c - 1);
    dfs(grid, r, c + 1);
}

private boolean inArea(char[][] grid, int r, int c) {
    return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}

进阶题目描述：给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的 数目 。

示例 :

输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。

思路：只要grid2的岛屿在grid1上是水域的话，就不是子岛屿，所以只需要在dfs搜索过程中判断是不是水域，如果不是水域，我们统计覆盖子岛屿的个数。

代码实现：

public boolean flag = false;
public int countSubIslands(int[][] grid1, int[][] grid2) {
    int m = grid2.length, n = grid2[0].length;
    int ans = 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid2[i][j] == 1) {
                flag = true;
                dfs(grid1, grid2, i, j);
                if (flag) {
                    ans++;
                }
            }
        }
    }
    return ans;
}

public void dfs(int[][] grid1, int[][] grid2, int r, int c) {
    if (!inArea(grid1, grid2, r, c) || grid2[r][c] != 1) {
        return;
    }
    // 标记为已遍历
    grid2[r][c] = 2;
    if (grid1[r][c] == 0) {
        flag = false;
    }
    dfs(grid1, grid2, r - 1, c);
    dfs(grid1, grid2, r + 1, c);
    dfs(grid1, grid2, r, c - 1);
    dfs(grid1, grid2, r, c + 1);
}

private boolean inArea(int[][] grid1, int[][] grid2, int r, int c) {
    return 0 <= r && r < grid1.length && 0 <= c && c < grid1[0].length;
}

2.岛屿的最大面积（695 - 中）

题目描述：给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例 :

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

思路：殊途同归，这里dfs返回的是四个方向岛屿的数量累加和。

代码实现：

public int maxAreaOfIsland(int[][] grid) {
    if (grid == null || grid.length == 0 || (grid.length == 1 && grid[0].length == 0)) {
        return 0;
    }
    int M = grid.length, N = grid[0].length;
    int max = 0;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 1) {
                int count = dfs(grid, i, j);
                max = Math.max(max, count);
            }
        }
    }
    return max;
}
private int dfs(int[][] grid, int r, int c) {
    if (!inArea(grid, r, c) || grid[r][c] != 1) return 0;
    grid[r][c] = 2; // 标记为已遍历

    return 1 +
    dfs(grid, r - 1, c) +
    dfs(grid, r + 1, c) +
    dfs(grid, r, c - 1) +
    dfs(grid, r, c + 1);
}
private boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}

3.填海造陆（827 - 难）

题目描述：在二维地图上， 0代表海洋， 1代表陆地，我们最多只能将一格 0 海洋变成 1变成陆地。

进行填海之后，地图上最大的岛屿面积是多少？（上、下、左、右四个方向相连的 1 可形成岛屿）

示例 :

输入: [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

思路：两遍DFS求解：

• 第一遍DFS：遍历陆地格子，计算岛屿的面积（同695题）并标记岛屿（岛屿内容更新为序号），
• 第二遍DFS：遍历海洋格子，连接某一点上下左右的陆地格子，四个方向用hashset去重（确保连接为有效区域并且不是海洋）。

作为上一题的升级版，想一下：如何检验要填充格子的相邻格子是否来自两个不同的岛屿。

可以使用岛屿序号与面积的对应关系：<key, value> -> 岛屿序号-岛屿面积

注意：0表示海洋，1表示陆地，所以岛屿的编号从2开始。

代码实现：

 public int largestIsland(int[][] grid) {
    if (grid==null || grid.length == 0){
        return 1;
    }

    int res = 0;
    int index = 2;  //index表示岛屿的编号，0是海洋1是陆地，从2开始遍历
    HashMap<Integer,Integer> indexAndAreas = new HashMap<>();   //岛屿编号：岛屿面积

    /**
     * 计算每个岛屿的面积，并标记是第几个岛屿
     */
    for (int r=0;r<grid.length;r++){
        for (int c=0;c<grid[0].length;c++){
            if (grid[r][c] == 1){
                int area = area(grid,r,c,index);    //返回每个岛屿的面积，dfs（其中该位置更新为岛屿编号）
                indexAndAreas.put(index,area);      //存入岛屿编号、岛屿面积
                index++;       //岛屿编号增加
                res = Math.max(res,area);   //记录最大的岛屿面积
            }
        }
    }

    if (res == 0) return 1;     //res=0表示没有陆地，那么造一块，则返回1即可

    /**
     * 遍历海洋格子，假设这个格子填充，那么就把上下左右是陆地的格子所在的岛屿连接起来
     */
    for (int r=0;r<grid.length;r++){
        for (int c=0;c<grid[0].length;c++){
            if (grid[r][c] == 0){ 
                HashSet<Integer> hashSet = findNeighbour(grid,r,c);//把上下左右邻居放入set去重
                if (hashSet.size() < 1) continue;    //如果海洋格子周围没有格子不必计算
                int twoIsland = 1;      //填充这个格子，初始为1，这个变量记录合并岛屿后的面积
                for (Integer i: hashSet){
                    twoIsland += indexAndAreas.get(i);  //该格子填充，则上下左右的陆地的都连接了，通过序号获得面积，加上面积
                }
                res = Math.max(res,twoIsland);  //比较得到最大的面积
            }
        }
    }
    return res;
}


/**
 * 对于海洋格子，找到上下左右
 * 每个方向，都要确保有效inArea以及是陆地格子，则表示是该海洋格子的陆地邻居(返回当前海洋格子的陆地邻居集合！)
 */
private HashSet<Integer> findNeighbour(int[][] grid,int r,int c){
    HashSet<Integer> hashSet = new HashSet<>();
    if (inArea(grid,r-1,c)&&grid[r-1][c] != 0){
        hashSet.add(grid[r-1][c]);
    }
    if (inArea(grid,r+1,c) && grid[r+1][c] != 0){
        hashSet.add(grid[r+1][c]);
    }
    if (inArea(grid,r,c-1) && grid[r][c-1] != 0){
        hashSet.add(grid[r][c-1]);
    }
    if (inArea(grid,r,c+1) && grid[r][c+1] != 0){
        hashSet.add(grid[r][c+1]);
    }
    return hashSet;
}

/**
 * dfs方法，将格子填充为index，即表示这个格子属于哪个岛的
 * 计算岛屿面积，上下左右，当然这个可以优化的，因为不需要计算上面的，会有重复
 */
private int area(int[][] grid, int r, int c,int index){
    if (!inArea(grid,r,c) || grid[r][c] != 1) return 0;
    grid[r][c] = index; //设置当前格子为某个岛屿编号

    return 1 + area(grid,r-1,c,index) + area(grid,r+1,c,index) + area(grid,r,c-1,index) + area(grid,r,c+1,index);
}

private boolean inArea(int[][] grid,int r,int c){
    return r>=0 && r<grid.length&&c>=0 && c<grid[0].length;
}

4.岛屿的周长（463 - 易）

题目描述：给定一个 row x col 的二维网格地图 grid ，其中：gridi = 1 表示陆地， gridi = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 :

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

思路：周长本质就是岛屿的边缘，计算岛屿的周长只有两种情况：一种是区域越界，另一种是遇到海洋。

代码实现：

public int islandPerimeter(int[][] grid) {
    if (grid == null || grid.length == 0 || (grid.length == 1 && grid[0].length == 0)) {
        return 0;
    }
    int M = grid.length, N = grid[0].length;
    int ans = 0;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 1) {
                ans = dfs(grid, i, j);
            }
        }
    }
    return ans;
}
private int dfs(int[][] grid, int r, int c) {
    if (!inArea(grid, r, c) || grid[r][c] == 0) return 1;
    if (grid[r][c] == 2) return 0;
    grid[r][c] = 2; // 标记为已遍历

    return
    dfs(grid, r - 1, c) +
    dfs(grid, r + 1, c) +
    dfs(grid, r, c - 1) +
    dfs(grid, r, c + 1);
}
private boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;
}