岛屿问题

发表于 | 分类于 ， ， |

回溯算法解决所有岛屿问题

200.岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        int res=0;
        //遍历grid
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    //每发现一个岛屿，岛屿数量+1
                    res++;
                    //然后使用dfs将岛屿淹了
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    //从grid[i][j]开始，将与之相邻的陆地变成海水
    void dfs(vector<vector<char>>& grid, int i, int j){
        int m=grid.size();
        int n=grid[0].size();
        if(i<0 || i>=m || j<0 || j>=n){
            //超出索引边界
            return;
        }
        if(grid[i][j]=='0'){
            //已经是海水了
            return;
        }
        //将grid[i][j]变成海水
        grid[i][j]='0';
        //淹没上下左右的陆地
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
};

1254.统计封闭岛屿的数量

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。

请返回 封闭岛屿 的数目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        int res=0;
        for(int i=0;i<m;i++){
            //把靠左边的岛屿淹掉
            dfs(grid, i, 0);
            //把靠右边的岛屿淹掉
            dfs(grid, i, n-1);
        }
        for(int j=0;j<n;j++){
            //把靠上边的岛屿淹掉
            dfs(grid, 0, j);
            //把靠下边的岛屿淹掉
            dfs(grid, m-1, j);
        }
        //遍历grid，剩下的岛屿都是封闭岛屿
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    //每发现一个岛屿，岛屿数量+1
                    res++;
                    //然后使用dfs将岛屿淹了
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
    //从grid[i][j]开始，将与之相邻的陆地变成海水
    void dfs(vector<vector<int>>& grid, int i, int j){
        int m=grid.size();
        int n=grid[0].size();
        //超出索引边界
        if(i<0 || i>=m || j<0 || j>=n){
            return;
        }
        if(grid[i][j]==1){
            //已经是海水了
            return;
        }
        //将grid[i][j]变成海水
        grid[i][j]=1;
        //淹没上下左右的陆地
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
};

1020.飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        int res=0;
        //将靠边的陆地淹掉
        for(int i=0;i<m;i++){
            dfs(grid, i, 0);
            dfs(grid, i, n-1);
        }
        for(int j=0;j<n;j++){
            dfs(grid, 0, j);
            dfs(grid, m-1, j);
        }
        //统计剩下的陆地数量
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    res++;
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& grid, int i, int j){
        int m=grid.size();
        int n=grid[0].size();
        if(i<0 || i>=m || j<0 || j>=n){
            return;
        }
        if(grid[i][j]==0){
            return;
        }
        grid[i][j]=0;
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
};

1905.统计子岛屿

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int m=grid1.size();
        int n=grid1[0].size();
        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){
                    //如果在grid1中是海水，在grid2中是陆地，肯定不是子岛屿，将其淹掉
                    dfs(grid2, i, j);
                }
            }
        }
        //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;
    }
    void dfs(vector<vector<int>>& grid, int i, int j){
        int m=grid.size();
        int n=grid[0].size();
        if(i<0 || i>=m || j<0 || j>=n){
            return;
        }
        if(grid[i][j]==0){
            return;
        }
        grid[i][j]=0;
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }
};

695.岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

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

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        int res=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    //淹没岛屿，并更新最大岛屿面积
                    res = max(res, dfs(grid, i, j));
                }
            }
        }
        return res;
    }
    //淹没与grid[i][j]相邻的陆地，并返回淹没的陆地面积
    int dfs(vector<vector<int>>& grid, int i, int j){
        int m=grid.size();
        int n=grid[0].size();
        if(i<0 || i>=m || j<0 || j>=n){
            //超出索引边界
            return 0;
        }
        if(grid[i][j]==0){
            //已经是海水了
            return 0;
        }
        //将grid[i][j]变成海水
        grid[i][j]=0;
        return dfs(grid, i-1, j) + dfs(grid, i+1, j) +
               dfs(grid, i, j-1) + dfs(grid, i, j+1) + 1;
    }
};
-------------本文结束 感谢阅读-------------
0%