力扣刷题-图论-岛屿类问题-集合实现（c++实现）

• 我的老师：力扣链接这道题题解中最高赞的回答nettee，从这篇题解中我学到了dfs框架以及解决思路，并独立完成了该题解里的几道习题
• 本人刷题的习惯是学会一个板子，然后之后的同类题都机械的用这个板子去做，最好不做创新，或许能给其他朋友提供一些规律性帮助，所以本blog把我各个题目的代码都放上来！

岛屿数量（简单）

岛屿数量

• 这道是母题，放代码（后面的题目我一律按照这个板子去做）

class Solution {
public:
    int num=0;
    int numIslands(vector<vector<char>>& grid) {
        int rn = grid.size();    // 行数
        int cn = grid[0].size(); // 列数
        for (int r = 0; r < rn; r++) {
            for (int c = 0; c < cn; c++) {
                // 先标记
                if (grid[r][c] == '1') {
                    num++;
                }
                dfs(grid, r, c);
            }
        }
        return num;
    }
    void dfs(vector<vector<char>>& grid, int r, int c) {
        if (!inArea(grid, r, c) || grid[r][c] != '1')
            return;
        grid[r][c]='2';
        //四面（上下左右）去dfs
        dfs(grid, r - 1, c );
        dfs(grid, r , c + 1);
        dfs(grid, r + 1, c );
        dfs(grid, r , c - 1);
    }
    bool inArea(vector<vector<char>>& grid, int r, int c) {
        return (0 <= r) && (r < grid.size()) && (0 <= c) &&
               (c < grid[0].size());
    }
};
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

岛屿周长（简单）

岛屿周长

• 很容易分析出来，对岛屿点（1）去上下左右dfs，如果是0或者不在Area内，就可以周长+1，最后累计获得总周长，放代码：

class Solution {
    // 遍历上下左右，如果是陆地就不动，如果是海或者不在area内就+1
    // 总共只有一个岛屿

public:
    int peri = 0;
    int islandPerimeter(vector<vector<int>>& grid) {
        int rn = grid.size();
        int cn = grid[0].size();
        for (int r = 0; r < rn; r++) {
            for (int c = 0; c < cn; c++) {
                // 如果是陆地
                if (grid[r][c] != 1) {
                    continue;
                }
                // 如果是陆地才会
                dfs(grid, r, c);
            }
        }
        return peri;
    }
    void dfs(vector<vector<int>>& grid, int r, int c) {
        // 还要考虑grid==[2]的情况

        if (!inArea(grid, r, c) || grid[r][c] == 0) {
            peri++;
            return;
        }

        if (grid[r][c] == 2) {
            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);
        return;
    }
    bool inArea(vector<vector<int>>& grid, int r, int c) {
        return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
    }
};
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

岛屿的最大面积（中等）

岛屿的最大面积
这道题的思路也很明显，同理找到所有的岛屿，然后开一个新的变量maxs来存最大岛屿就OK，看代码：

• 此处dfs有点不同，返回值为int，然后直接 把上下左右的dfs写在return里，大家看代码应该很好理解（其实上一题求周长也可以这样做，这里周长一道，面积一道，提供两种方案）

class Solution {
public:
    int maxs = 0;
    int s = 0;

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        // 同理
        int rn = grid.size();
        int cn = grid[0].size();
        for (int r = 0; r < rn; r++) {
            for (int c = 0; c < cn; c++) {
                if (grid[r][c] != 1)
                    continue;
                s = dfs(grid, r, c);
                maxs = s > maxs ? s : maxs;
            }
        }
        return maxs;
    }
    int dfs(vector<vector<int>>& grid, int r, int c) {
        if (!InArea(grid, r, c)) {
            return 0;
        }
        // 如果是海
        if (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);
    }
    bool InArea(vector<vector<int>>& grid, int r, int c) {
        return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
    }
};
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

最大人工岛（困难）

最大人工岛

• 本题我一开始的思路是：遍历每个0点，然后赋值为1，再遍历该情况下的最大岛屿面积（类似上一题思路）；再把该1变回0，看下一个变1的可能点；取所有情况的面积最大值——无奈空间超限！
• 于是我看了题解，理解了以后又自己写，与官方题解的代码略有不同，更贴近我爱用的板子（与上面几道吻合）
• 思路：
  • 先计算出每一个岛屿的面积（防止之后重复计算）——第一次双重循环
  • 第二次双重循环思路同理，把0变成1，看是否能连接一些岛屿
  • 已写明注释！
  • ps. 这份代码巧用vector< int > d = {0, -1, 0, 1, 0};，大家可以好好看下，和dfs(grid,r-1,s)等上下左右遍历异曲同工，适用于减少递归，代码更清晰

class Solution {
public:
    int t = 0;
    vector<int> square;//存储每一个岛屿的面积
    vector<int> d = {0, -1, 0, 1, 0};
    int zero=0;//是否有0可以变1，如果没有的话就说明给的vector是全1，直接返回总面积！）
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        // 先计算每个岛屿的面积吧
        vector<vector<int>> used(n,vector<int>(n));
       square.resize(n * n + 2, 0);//这行相当于是一个经验吧，
       //否则报错（看我上一篇博客）
        int r = 0, c = 0, x1 = 0, y1 = 0, s = 0, maxs = 0;
        for (r = 0; r < n; r++) {
            for (c = 0; c < n; c++) {
                // 如果就是大陆
                if (grid[r][c] == 1) {
                    t++;//注意，这里我本来想让t从0开始的，后来发现不行，
                    //因为如果没有标记的岛屿也是0，之后用t来索引的时候会出错
                    square[t] = dfs(grid, r, c, t, used);
                    //这里得到岛屿面积
                }
            }
        }
        unordered_set<int> connected;
        // 现在完成面积的计算
        for (r = 0; r < n; r++) {
            for (c = 0; c < n; c++) {
                if (grid[r][c] == 0) {
                //说明该vector并非全1
                    zero=1;
                    //面积
                    s = 1;
                    connected.clear();
                    // 尝试变成1，看着附近的area
                    for (int i = 0; i < 4; i++) {
                        x1 = r + d[i];
                        y1 = c + d[i + 1];
                        if (InArea(grid,x1,y1)&&used[x1][y1] != 0 &&
                            connected.count(used[x1][y1]) == 0) {
                            // s面积加上来
                            s += square[used[x1][y1]];
                            connected.insert(used[x1][y1]);
                        }
                    }
                    // 该情况的面积计算完毕
                    maxs = max(s, maxs);
                }
            }
        }
        //如果是全1的话就直接返回square[1]
        return zero==0?square[1]:maxs;
    }
//dfs功效纯粹为了计算每个岛屿的面积！
    int dfs(vector<vector<int>>& grid, int r, int c, int t,
            vector<vector<int>>& used) {
        if (!InArea(grid, r, c) || used[r][c] != 0 || grid[r][c] != 1)
            return 0;
        used[r][c] = t;
        int x1, y1, s = 1;
        // 已经遍历过就标记为2
        grid[r][c] = 2;
        for (int i = 0; i < 4; i++) {
            x1 = r + d[i], y1 = c + d[i + 1];
            s += dfs(grid, x1, y1, t, used);
        }

        return s;
    }

    bool InArea(vector<vector<int>>& grid, int r, int c) {
        return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
    }
};

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75