https://www.programmercarl.com/kamacoder/0104.%E5%BB%BA%E9%80%A0%E6%9C%80%E5%A4%A7%E5%B2%9B%E5%B1%BF.html

1.本题我做了好久，思考了很长时间，这个优化的思路确实是很巧妙只不过真的对于现在的我来说着实挺难的，本题我分了两步写的，第一步统计每个子岛的大小并且打上对应的标记数，然后第二步再遍历整个岛屿里面是0的位置然后遍历这个水节点的四周，分别判断是否遇到我们已经收集好的子岛，遇到了就计数器cnt += gridNum[grid[nexti][nextj]]然后再将该标号的岛屿插入到我们遍历过的visitedgrid里面这样由于这个visitedgrid是一个unordered_set还可以去重，这样就统计好周围的岛屿连接在一起的最大面积用res去承接最大值，别忘了判断条件，要是该岛屿访问过就跳过本次循环。思路厘清就很好做，我用了小2个小时来研究透该题，本题真的是一个大综合很考验对于思路的理解和dfs的理解，二刷我要再来挑战一次这个题。

CPP

#include<bits/stdc++.h>
using namespace std;
int cnt;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark){
    if(visited[x][y] || grid[x][y] == 0)return ;
    visited[x][y] = true;
    grid[x][y] = mark;
    cnt++;
    for(int i = 0; i < 4; i++){
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        
        if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())continue;
        dfs(grid, visited, nextx, nexty, mark);
    }
    
}


int main(){
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grid(n, vector<int>(m, 0));
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> grid[i][j];
        }
    }
    
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    unordered_map<int, int> gridNum;
    
    int mark = 2;
    bool isfullgrid = true;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 0)isfullgrid = false;
            if(!visited[i][j] && grid[i][j] == 1){
                cnt = 0;
                dfs(grid, visited, i, j, mark);
                gridNum[mark] = cnt;
                mark++;
            }
        }
    }
    
    if(isfullgrid){
        cout << n * m << endl;
        return 0;
    }
    
    int res = 0;
    unordered_set<int> visitedgrid;
    
    for(int i = 0 ; i < n; i++){
        for(int j = 0; j < m; j++){
            cnt = 1;
            visitedgrid.clear();
            if(grid[i][j] == 0){
                for(int k = 0; k < 4; k++){
                    int nexti = i + dir[k][0];
                    int nextj = j + dir[k][1];
                    
                    if(nexti < 0 || nexti >= grid.size() || nextj < 0 || nextj >= grid[0].size())continue;
                    if(visitedgrid.count(grid[nexti][nextj]))continue;
                    cnt += gridNum[grid[nexti][nextj]];
                    visitedgrid.insert(grid[nexti][nextj]);
                }
            }
            res = max(res, cnt);
        }
    }
    cout << res << endl;
    
}

下面这个代码是对于这两个代码就是在处理每个岛屿的面积的地方的处理逻辑不同，我的代码是判断完这个事陆地然后cnt直接置为1然后将该节点置为true表示访问过了然后进入dfs然后进入dfs之后判断邻居节点是否为陆地然后计数，将是陆地的邻居节点都记为对应的mark。

#include<bits/stdc++.h>
using namespace std;
int cnt;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y, int mark){
    for(int i = 0; i < 4; i++){
        int nextx = x + dir[i][0];
        int nexty = y + dir[i][1];
        
        if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())continue;
        if(!visited[nextx][nexty] && grid[nextx][nexty] == 1){
            visited[nextx][nexty] = true;
            grid[nextx][nexty] = mark;
            cnt++;
            dfs(grid, visited, nextx, nexty, mark);

        }
    }
    
}


int main(){
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grid(n, vector<int>(m, 0));
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> grid[i][j];
        }
    }
    
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    unordered_map<int, int> gridNum;
    
    int mark = 2;
    bool isfullgrid = true;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(grid[i][j] == 0)isfullgrid = false;
            if(!visited[i][j] && grid[i][j] == 1){
                cnt = 1;
                visited[i][j] = true;
                grid[i][j] = mark;
                dfs(grid, visited, i, j, mark);
                gridNum[mark] = cnt;
                mark++;
            }
        }
    }
    
    if(isfullgrid){
        cout << n * m << endl;
        return 0;
    }
    
    int res = 0;
    unordered_set<int> visitedgrid;
    
    for(int i = 0 ; i < n; i++){
        for(int j = 0; j < m; j++){
            cnt = 1;
            visitedgrid.clear();
            if(grid[i][j] == 0){
                for(int k = 0; k < 4; k++){
                    int nexti = i + dir[k][0];
                    int nextj = j + dir[k][1];
                    
                    if(nexti < 0 || nexti >= grid.size() || nextj < 0 || nextj >= grid[0].size())continue;
                    if(visitedgrid.count(grid[nexti][nextj]))continue;
                    cnt += gridNum[grid[nexti][nextj]];
                    visitedgrid.insert(grid[nexti][nextj]);
                }
            }
            res = max(res, cnt);
        }
    }
    cout << res << endl;
    
}