如果你一点也不了解什么是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 这个要判断是因为我写的时候没有加入填的陆地，所以要判断一下。
我的写法只是我目前能想到的思路的直接写法，没有什么优化，期望大家有更优化的思路或者写法可以私信或评论区留言