[bfs][dfs]面试题 16.19. 水域大小(medium)

水域大小(medium)"/>

[bfs][dfs]面试题 16.19. 水域大小(medium)

题目：

题解：

bfs dfs 纯模板题，思路看代码即可。

代码如下：

// 方向数组，由于对角线也算水域范围，所以为8个方向
int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
// 用来标记水域是否被统计过
bool flag[1010][1010];class Solution {
public:void dfs(vector<vector<int>>& land,int i,int j,int& val,int n,int m){// 给(i,j)标记，并将水域小大+1val++;flag[i][j]=1;// 进行8个方向的dfsfor(int k=0;k<8;++k){int x=i+dx[k],y=j+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&!land[x][y]&&!flag[x][y])dfs(land,x,y,val,n,m);}}// 题解1：dfsvector<int> pondSizes_1(vector<vector<int>>& land) {memset(flag,0,sizeof flag);vector<int> res;int 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]&&!flag[i][j])// (i,j)为水域并且没被统计过{int val=0;dfs(land,i,j,val,n,m);res.push_back(val);}sort(res.begin(),res.end());return res;}// 题解2：bfsvector<int> pondSizes(vector<vector<int>>& land){memset(flag,0,sizeof flag);vector<int> res;int 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]&&!flag[i][j]){res.push_back(bfs(land,i,j,n,m));}}sort(res.begin(),res.end());return res;}int bfs(vector<vector<int>>& land,int i,int j,int n,int m){int val=0;queue<pair<int,int>> q;flag[i][j]=1;q.push({i,j});// 进行bfswhile(!q.empty()){auto t=q.front();q.pop();val++;for(int k=0;k<8;++k){int x=t.first+dx[k],y=t.second+dy[k];// 将没有被访问过的点加入if(x>=0&&x<n&&y>=0&&y<m&&!land[x][y]&&!flag[x][y]){flag[x][y]=1;q.push({x,y});}}}return val;}
};