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

• 我的老师：力扣链接这道题题解中最高赞的回复nettee，从这篇题解中我学到了dfs框架以及办理思绪，并独立完成了该题解里的几道习题
  
• 本人刷题的风俗是学会一个板子，然后之后的同类题都机器的用这个板子去做，最好不做创新，大概能给其他朋侪提供一些规律性资助，以是本blog把我各个标题的代码都放上来！
  

岛屿数目（简单）

岛屿数目

• 这道是母题，放代码（背面的标题我划一按照这个板子去做）
  

1. class Solution {
2. public:
3.     int num=0;
4.     int numIslands(vector<vector<char>>& grid) {
5.         int rn = grid.size();    // 行数
6.         int cn = grid[0].size(); // 列数
7.         for (int r = 0; r < rn; r++) {
8.             for (int c = 0; c < cn; c++) {
9.                 // 先标记
10.                 if (grid[r][c] == '1') {
11.                     num++;
12.                 }
13.                 dfs(grid, r, c);
14.             }
15.         }
16.         return num;
17.     }
18.     void dfs(vector<vector<char>>& grid, int r, int c) {
19.         if (!inArea(grid, r, c) || grid[r][c] != '1')
20.             return;
21.         grid[r][c]='2';
22.         //四面（上下左右）去dfs
23.         dfs(grid, r - 1, c );
24.         dfs(grid, r , c + 1);
25.         dfs(grid, r + 1, c );
26.         dfs(grid, r , c - 1);
27.     }
28.     bool inArea(vector<vector<char>>& grid, int r, int c) {
29.         return (0 <= r) && (r < grid.size()) && (0 <= c) &&
30.                (c < grid[0].size());
31.     }
32. };

复制代码

岛屿周长（简单）

岛屿周长

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

1. class Solution {
2.     // 遍历上下左右，如果是陆地就不动，如果是海或者不在area内就+1
3.     // 总共只有一个岛屿
5. public:
6.     int peri = 0;
7.     int islandPerimeter(vector<vector<int>>& grid) {
8.         int rn = grid.size();
9.         int cn = grid[0].size();
10.         for (int r = 0; r < rn; r++) {
11.             for (int c = 0; c < cn; c++) {
12.                 // 如果是陆地
13.                 if (grid[r][c] != 1) {
14.                     continue;
15.                 }
16.                 // 如果是陆地才会
17.                 dfs(grid, r, c);
18.             }
19.         }
20.         return peri;
21.     }
22.     void dfs(vector<vector<int>>& grid, int r, int c) {
23.         // 还要考虑grid==[2]的情况
25.         if (!inArea(grid, r, c) || grid[r][c] == 0) {
26.             peri++;
27.             return;
28.         }
30.         if (grid[r][c] == 2) {
31.             return;
32.         }
34.         grid[r][c] = 2;
35.         dfs(grid, r - 1, c);
36.         dfs(grid, r + 1, c);
37.         dfs(grid, r, c - 1);
38.         dfs(grid, r, c + 1);
39.         return;
40.     }
41.     bool inArea(vector<vector<int>>& grid, int r, int c) {
42.         return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
43.     }
44. };

复制代码

岛屿的最大面积（中等）

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

• 此处dfs有点差别，返回值为int，然后直接 把上下左右的dfs写在return里，各人看代码应该很好明白（实在上一题求周长也可以如许做，这里周长一道，面积一道，提供两种方案）
  

1. class Solution {
2. public:
3.     int maxs = 0;
4.     int s = 0;
6.     int maxAreaOfIsland(vector<vector<int>>& grid) {
7.         // 同理
8.         int rn = grid.size();
9.         int cn = grid[0].size();
10.         for (int r = 0; r < rn; r++) {
11.             for (int c = 0; c < cn; c++) {
12.                 if (grid[r][c] != 1)
13.                     continue;
14.                 s = dfs(grid, r, c);
15.                 maxs = s > maxs ? s : maxs;
16.             }
17.         }
18.         return maxs;
19.     }
20.     int dfs(vector<vector<int>>& grid, int r, int c) {
21.         if (!InArea(grid, r, c)) {
22.             return 0;
23.         }
24.         // 如果是海
25.         if (grid[r][c] != 1) {
26.             return 0;
27.         }
28.         grid[r][c] = 2;
29.         return 1 + dfs(grid, r - 1, c) + dfs(grid, r + 1, c) +
30.                dfs(grid, r, c - 1) + dfs(grid, r, c + 1);
31.     }
32.     bool InArea(vector<vector<int>>& grid, int r, int c) {
33.         return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
34.     }
35. };

复制代码

最大人工岛（困难）

最大人工岛

• 本题我一开始的思绪是：遍历每个0点，然后赋值为1，再遍历该情况下的最大岛屿面积（雷同上一题思绪）；再把该1变回0，看下一个变1的大概点；取全部情况的面积最大值——无奈空间超限！
  
• 于是我看了题解，明白了以后又本身写，与官方题解的代码略有差别，更贴近我爱用的板子（与上面几道符合）
  
• 思绪：
  
  
  
  • 先盘算出每一个岛屿的面积（防止之后重复盘算）——第一次双重循环
    
  • 第二次双重循环思绪同理，把0变成1，看是否能毗连一些岛屿
    
  • 已写明解释！
    
  • ps. 这份代码巧用vector< int > d = {0, -1, 0, 1, 0};，各人可以好悦目下，和dfs(grid,r-1,s)等上下左右遍历异曲同工，实用于淘汰递归，代码更清晰
    
  
  

1. class Solution {
2. public:
3.     int t = 0;
4.     vector<int> square;//存储每一个岛屿的面积
5.     vector<int> d = {0, -1, 0, 1, 0};
6.     int zero=0;//是否有0可以变1，如果没有的话就说明给的vector是全1，直接返回总面积！）
7.     int largestIsland(vector<vector<int>>& grid) {
8.         int n = grid.size();
9.         // 先计算每个岛屿的面积吧
10.         vector<vector<int>> used(n,vector<int>(n));
11.        square.resize(n * n + 2, 0);//这行相当于是一个经验吧，
12.        //否则报错（看我上一篇博客）
13.         int r = 0, c = 0, x1 = 0, y1 = 0, s = 0, maxs = 0;
14.         for (r = 0; r < n; r++) {
15.             for (c = 0; c < n; c++) {
16.                 // 如果就是大陆
17.                 if (grid[r][c] == 1) {
18.                     t++;//注意，这里我本来想让t从0开始的，后来发现不行，
19.                     //因为如果没有标记的岛屿也是0，之后用t来索引的时候会出错
20.                     square[t] = dfs(grid, r, c, t, used);
21.                     //这里得到岛屿面积
22.                 }
23.             }
24.         }
25.         unordered_set<int> connected;
26.         // 现在完成面积的计算
27.         for (r = 0; r < n; r++) {
28.             for (c = 0; c < n; c++) {
29.                 if (grid[r][c] == 0) {
30.                 //说明该vector并非全1
31.                     zero=1;
32.                     //面积
33.                     s = 1;
34.                     connected.clear();
35.                     // 尝试变成1，看着附近的area
36.                     for (int i = 0; i < 4; i++) {
37.                         x1 = r + d[i];
38.                         y1 = c + d[i + 1];
39.                         if (InArea(grid,x1,y1)&&used[x1][y1] != 0 &&
40.                             connected.count(used[x1][y1]) == 0) {
41.                             // s面积加上来
42.                             s += square[used[x1][y1]];
43.                             connected.insert(used[x1][y1]);
44.                         }
45.                     }
46.                     // 该情况的面积计算完毕
47.                     maxs = max(s, maxs);
48.                 }
49.             }
50.         }
51.         //如果是全1的话就直接返回square[1]
52.         return zero==0?square[1]:maxs;
53.     }
54. //dfs功效纯粹为了计算每个岛屿的面积！
55.     int dfs(vector<vector<int>>& grid, int r, int c, int t,
56.             vector<vector<int>>& used) {
57.         if (!InArea(grid, r, c) || used[r][c] != 0 || grid[r][c] != 1)
58.             return 0;
59.         used[r][c] = t;
60.         int x1, y1, s = 1;
61.         // 已经遍历过就标记为2
62.         grid[r][c] = 2;
63.         for (int i = 0; i < 4; i++) {
64.             x1 = r + d[i], y1 = c + d[i + 1];
65.             s += dfs(grid, x1, y1, t, used);
66.         }
68.         return s;
69.     }
71.     bool InArea(vector<vector<int>>& grid, int r, int c) {
72.         return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
73.     }
74. };

复制代码