水域大小（DFS）

水域大小（DFS）

 该题有点像做过的“岛屿数量”，也是标准的模板题，按照模板Go！！！！！！！！！！！！！

岛屿数量（DFS / BFS）_ZZZWWWFFF_的博客-CSDN博客

class Solution {
public:vector<int> v;int tx,ty,n,m,c=0,nextt[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};int dfs(vector<vector<int>>& land,int x,int y){if(land[x][y]==0){land[x][y]=-1;//走过的地方做记号c++;//水域数for(int i=0;i<8;i++){tx=x+nextt[i][0];ty=y+nextt[i][1];if(tx<0||ty<0||tx>=n||ty>=m){continue;}dfs(land,tx,ty);}}return c;}vector<int> pondSizes(vector<vector<int>>& land) {n=land.size();m=land[0].size();for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(land[i][j]==0)//遇到水域就进入搜索并且计算水域数量{c=0;v.push_back(dfs(land,i,j));}}}sort(v.begin(),v.end());排序return v;}};

下面是我在题解中看到的一份我觉得不错的题解，分享给大家（大致思路差不多） 

class Solution {
public:vector<int> ret;int ans;vector<int> pondSizes(vector<vector<int>>& land) {for(int i=0;i<land.size();i++){for(int j=0;j<land[i].size();j++){if(!land[i][j]){ans = 0;dfs(land, i, j);ret.push_back(ans);}}}sort(ret.begin(),d());return ret;}void dfs(vector<vector<int>>& land, int x, int y){if(x < 0 || x >= land.size() || y < 0 || y >= land[x].size() || land[x][y]){return;}if(!land[x][y]){ans++;}land[x][y]--;//走过做记号dfs(land, x-1, y);dfs(land, x-1, y-1);dfs(land, x-1, y+1);dfs(land, x, y-1);dfs(land, x, y+1);dfs(land, x+1, y-1);dfs(land, x+1, y);dfs(land, x+1, y+1);}
};