面试题 16.19. 水域大小
难度中等25收藏分享切换为英文关注反馈
你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
示例：
输入： [[0,2,1,0],[0,1,0,1],[1,1,0,1],[0,1,0,1] ] 输出： [1,2,4]
提示：
0 < len(land) <= 10000 < len(land[i]) <= 1000
解题思路：经典的DFS解法，
AC代码如下：
class Solution {
public:
vector<int> Pools;
int vis[1000][1000];
int cnt=0;
void DFS(int x,int y,int row,int line){
cnt++;
vis[x][y]++;
for(int i=max(x-1,0);i<=min(row-1,x+1);i++){
for(int j=max(0,y-1);j<=min(line-1,y+1);j++){
if( vis[i][j]==0)//未被访问过的点
DFS(i,j,row,line);
}
}
}
vector<int> pondSizes(vector<vector<int>>& land) {
int row=land.size();//行
int line=land[0].size();//列
for(int i=0;i<land.size();i++){
for(int j=0;j<land[i].size();j++){
vis[i][j]=land[i][j];
}
}
for(int i=0;i<land.size();i++){
for(int j=0;j<land[i].size();j++){
if(vis[i][j]==0 ){
DFS(i,j,row,line);
Pools.push_back(cnt);
cnt=0;
}
}
}
sort(Pools.begin(),Pools.end());
return Pools;
}
};