如果你一点也不了解什么是DFS(深度优先搜索)，建议看一下这一篇LeetCode岛屿问题DFS

最大人工岛

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
来源：力扣（LeetCode）最大人工岛

我们以下图来分析：

思路：我们不难想到，这一题主要就是改变一个海洋’0’变成陆地’1’，我们可以计算每个陆地的大小，然后在其周围寻找是否有相邻的陆地，相加再判断其大小是否是最大的，这样一个一个暴力遍历，就可以AC了。

我们首先要写一个搜寻该陆地的大小：

int max_size(vector<vector<int>>& grid,int i,int j,int n)
{if(i<0 || i>=grid.size() || j<0 || j>=grid.size() || grid[i][j]!=1){return 0;}grid[i][j]=n;return 1 + max_size(grid,i+1,j,n)+max_size(grid,i-1,j,n)+max_size(grid,i,j+1,n)+max_size(grid,i,j-1,n);
}

这里我们将已经遍历过的陆地更改为数字也是有讲究的：
假如一开始是这样的：

如果我们直接以它们的最大面积的大小来代替它们的陆地编号比如：

但是下面情况我们不好去处理：

所以，我们可以将更改的陆地数字作为下标，面积大小存储与数组中，与下标对应，这样我们就能很好处理上述，一块陆地计算两次情况。

接下来我们就

• 要么继续遍历陆地格子，然后在其判断边界是否为海洋格子的时候进行处理
• 要么我们直接遍历海洋格子，然后在海洋格子的四周搜寻陆地

我的建议是遍历海洋格子，因为要继续遍历陆地格子，那么我们又要进DFS递归，这种递归的边界判断很难把握。

int judge(vector<vector<int>>& grid,vector<int>& arr,int i,int j)
{int sum=0;vector<int> _arr;if(tof(grid,i-1,j) && find(_arr.begin(),_arr.end(),grid[i-1][j])==_arr.end() && grid[i-1][j]!=0){sum+=arr[grid[i-1][j]-2];_arr.push_back(grid[i-1][j]);}if(tof(grid,i+1,j) && find(_arr.begin(),_arr.end(),grid[i+1][j])==_arr.end() && grid[i+1][j]!=0){sum+=arr[grid[i+1][j]-2];_arr.push_back(grid[i+1][j]);}if(tof(grid,i,j-1) && find(_arr.begin(),_arr.end(),grid[i][j-1])==_arr.end() && grid[i][j-1]!=0){sum+=arr[grid[i][j-1]-2];_arr.push_back(grid[i][j-1]);}if(tof(grid,i,j+1) && find(_arr.begin(),_arr.end(),grid[i][j+1])==_arr.end() && grid[i][j+1]!=0){sum+=arr[grid[i][j+1]-2];_arr.push_back(grid[i][j+1]);}return sum;
}

我的思路就是直接暴力搜索上下左右，然后将已加过的陆地存入临时数组来判断，避免增加重复陆地的情况。

最终代码：

class Solution {
public://DFS返回面积int max_size(vector<vector<int>>& grid,int i,int j,int n){if(i<0 || i>=grid.size() || j<0 || j>=grid.size() || grid[i][j]!=1){return 0;}grid[i][j]=n;return 1 + max_size(grid,i+1,j,n)+max_size(grid,i-1,j,n)+max_size(grid,i,j+1,n)+max_size(grid,i,j-1,n);}//判断海洋四周面积总和int judge(vector<vector<int>>& grid,vector<int>& arr,int i,int j){int sum=0;vector<int> _arr;if(tof(grid,i-1,j) && find(_arr.begin(),_arr.end(),grid[i-1][j])==_arr.end() && grid[i-1][j]!=0){sum+=arr[grid[i-1][j]-2];_arr.push_back(grid[i-1][j]);}if(tof(grid,i+1,j) && find(_arr.begin(),_arr.end(),grid[i+1][j])==_arr.end() && grid[i+1][j]!=0){sum+=arr[grid[i+1][j]-2];_arr.push_back(grid[i+1][j]);}if(tof(grid,i,j-1) && find(_arr.begin(),_arr.end(),grid[i][j-1])==_arr.end() && grid[i][j-1]!=0){sum+=arr[grid[i][j-1]-2];_arr.push_back(grid[i][j-1]);}if(tof(grid,i,j+1) && find(_arr.begin(),_arr.end(),grid[i][j+1])==_arr.end() && grid[i][j+1]!=0){sum+=arr[grid[i][j+1]-2];_arr.push_back(grid[i][j+1]);}return sum;}bool tof(vector<vector<int>>& grid,int i,int j){if(i<0 || i>=grid.size() || j<0 || j>=grid.size()){return false;}return true;}int largestIsland(vector<vector<int>>& grid) {vector<int> arr;int x=2;//第一次循环是用来找寻各个陆地面积，以及将面积大小存入以其陆地数字为下标的数组for(int i=0;i<grid.size();i++){for(int j=0;j<grid.size();j++){if(grid[i][j]==1){int sum=max_size(grid,i,j,x);x++;arr.push_back(sum);}}}//第二次循环是用来找寻最大面积int max=0;for(int i=0;i<grid.size();i++){for(int j=0;j<grid.size();j++){if(grid[i][j]==0){int sum = judge(grid,arr,i,j);if(sum>max){max=sum;}}}}if(arr.empty()){return 1;}if(max==0){return grid.size()*grid.size();}return max<(grid.size()*grid.size())?max+1:max;}
};

最后的判断，如果grid没有陆地，我们自己会填入一个陆地，所以要返回1。
max==0 是有可能没有海洋格子，循环没有进去，所以max=0，实则是满陆地格子
max<(grid.size()*grid.size())?max+1:max 这个要判断是因为我写的时候没有加入填的陆地，所以要判断一下。

我的写法只是我目前能想到的思路的直接写法，没有什么优化，期望大家有更优化的思路或者写法可以私信或评论区留言🚀🚀🚀