岛屿问题

岛屿问题

• • • 200.岛屿问题
    • 1254. 统计封闭岛屿的数目
    • 695. 岛屿的最大面积
    • 1905. 统计子岛屿

力扣上岛屿系列问题。

200.岛屿问题

解题思路：

1. 利用 DFS（深度优先搜索）根据题意计算岛屿数量。（简单易懂）
2. DFS 是沿着任意一个单元格上，下， 左， 右 遍历的，不能斜着遍历。
3. 将计算过的岛屿淹没掉防止重复计算。

class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length; //记录行列
        int res = 0;
		//遍历表格，挨着的岛屿为整个岛屿，所以记录完岛屿个数继续调用 DFS 进一步覆盖相邻岛屿
        for(int i =0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    res++;

                    dfs(grid,i,j);
                }

            }
        }
        return res;
    }

    public void dfs(char[][]grid, int i, int j){

        int m = grid.length, n = grid[0].length;
        
        if(i < 0 || j < 0 || i >= m || j >= n) return; //超出边界
        
        if (grid[i][j] == '0') {
        // 已经是海水了
        return;
    }
		
        // 如果是陆地，就淹没陆地。（此时已经记录过这个单元格了）
        grid[i][j] = '0';
        
        // 淹没上下左右的陆地
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);

    }
}

1254. 统计封闭岛屿的数目

解题思路：

1. DFS
2. 不同的是这道题求封闭岛屿的数量，我们先把表格外圈土地淹没，剩下的就是封闭岛屿。

class Solution {
    public int closedIsland(int[][] grid) {
    
        int m = grid.length, n = grid[0].length;
        int res = 0;
        
        //遍历表格，先把表格外圈土地淹没，剩下的就是封闭岛屿。
        for(int j = 0 ; j < n; j++){
            dfs(grid, 0, j);
            dfs(grid, m - 1, j);
        }

        for(int i = 0 ; i < m; i++){
            dfs(grid, i, 0);
            dfs(grid, i, n-1);
        } 

    // 遍历 grid，剩下的岛屿都是封闭岛屿
    //挨着的岛屿为整个岛屿，所以记录完岛屿个数继续调用 DFS 进一步覆盖相邻岛屿
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                res++;
                
                dfs(grid, i, j);
            }
        }
    }
    return res;
    }


public void dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {  //超出边界
        return;
    }
    if (grid[i][j] == 1) {
        // 已经是海水了
        return;
    }
    // 如果是陆地，就淹没陆地。（此时已经记录过这个单元格了）
    grid[i][j] = 1;
    
    // 淹没上下左右的陆地
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}
}

695. 岛屿的最大面积

解题思路：

1. DFS
2. 求最大面积岛屿，对整个表格遍历，不断更新最大值，剩下的和之前一样。

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
    // 记录岛屿的最大面积
    int res = 0;
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if(grid[i][j] == 1){
                res = Math.max(res, dfs(grid, i, j)); //记录面积最大的岛屿
            }
        }
    }
    return res;
}

public int dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        // 超出索引边界
        return 0;
    }
    if (grid[i][j] == 0) {
        // 已经是海水了
        return 0;
    }
    
    // 如果是陆地，就淹没陆地。（此时已经记录过这个单元格了）
    grid[i][j] = 0;  //防止重复计算

    return dfs(grid, i + 1, j) //我们只要知道返回的是面积最大岛屿的数值，剩下的交个 DFS
         + dfs(grid, i, j + 1)
         + dfs(grid, i - 1, j)
         + dfs(grid, i, j - 1) + 1;
	}
}

1905. 统计子岛屿

解题思路：

1. DFS
2. 求两个 grid 重叠的子岛屿。
3. 忽略 grid2 中是陆地的且 grid1 中是海水的子集，剩下的就是子岛屿

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
    
        int m = grid1.length, n = grid1[0].length;
        int res = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid1[i][j] == 0 && grid2[i][j] == 1)
                dfs(grid2, i , j); // 除去grid2 中是陆地的且 grid1 中是海水的子集，剩下的就是子岛屿
            }
        }
        

        // 现在 grid2 中剩下的岛屿都是子岛，计算岛屿数量
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid2[i][j] == 1) {
                    res++;
                    dfs(grid2, i, j);
                }
            }
        }
        return res;
    }

    
    public void dfs(int[][] grid, int i, int j) {
        int m = grid.length, n = grid[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            return;
        }
        if (grid[i][j] == 0) {
            return;
        }

        grid[i][j] = 0;
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}

引用:
fucking-algorithm