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

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

岛屿数量（简单）

岛屿数量

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

classSolution{public:int num=0;intnumIslands(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;}voiddfs(vector<vector<char>>& grid,int r,int c){if(!inArea(grid, r, c)|| grid[r][c]!='1')return;
        grid[r][c]='2';//四面（上下左右）去dfsdfs(grid, r -1, c );dfs(grid, r , c +1);dfs(grid, r +1, c );dfs(grid, r , c -1);}boolinArea(vector<vector<char>>& grid,int r,int c){return(0<= r)&&(r < grid.size())&&(0<= c)&&(c < grid[0].size());}};

岛屿周长（简单）

岛屿周长

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

classSolution{// 遍历上下左右，如果是陆地就不动，如果是海或者不在area内就+1// 总共只有一个岛屿public:int peri =0;intislandPerimeter(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;}voiddfs(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;}boolinArea(vector<vector<int>>& grid,int r,int c){return0<= r && r < grid.size()&&0<= c && c < grid[0].size();}};

岛屿的最大面积（中等）

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

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

classSolution{public:int maxs =0;int s =0;intmaxAreaOfIsland(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;}intdfs(vector<vector<int>>& grid,int r,int c){if(!InArea(grid, r, c)){return0;}// 如果是海if(grid[r][c]!=1){return0;}
        grid[r][c]=2;return1+dfs(grid, r -1, c)+dfs(grid, r +1, c)+dfs(grid, r, c -1)+dfs(grid, r, c +1);}boolInArea(vector<vector<int>>& grid,int r,int c){return0<= r && r < grid.size()&&0<= c && c < grid[0].size();}};

最大人工岛（困难）

最大人工岛

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

classSolution{public:int t =0;
    vector<int> square;//存储每一个岛屿的面积
    vector<int> d ={0,-1,0,1,0};int zero=0;//是否有0可以变1，如果没有的话就说明给的vector是全1，直接返回总面积！）intlargestIsland(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，看着附近的areafor(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功效纯粹为了计算每个岛屿的面积！intdfs(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)return0;
        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;}boolInArea(vector<vector<int>>& grid,int r,int c){return0<= r && r < grid.size()&&0<= c && c < grid[0].size();}};