题目(图的连通块的大小)

你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

示例：
输入：
[
[0,2,1,0],
[0,1,0,1],
[1,1,0,1],
[0,1,0,1]
]
输出： [1,2,4]

题解：

图的连通性，用DFS再合适不过。

const int dx[] = {-1,0,1,0,-1,-1,1,1};
const int dy[] = {0,1,0,-1,-1,1,-1,1};class Solution {
public:vector<int> ans;vector<vector<int>> land;int m,n;bool visited[1010][1010];vector<int> pondSizes(vector<vector<int>>& land) {this->land = land;m = (int)land.size();n = (int)land[0].size();ans.clear();memset(visited, 0, sizeof(visited));for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(land[i][j] || visited[i][j]){continue;}//第一个点要注意int cnt = 1;visited[i][j] = 1;dfs(i, j, cnt);ans.push_back(cnt);}}sort(ans.begin(), ans.end());return ans;}void dfs(int x,int y,int &cnt){for(int i=0;i<8;i++){int nx = x + dx[i];int ny = y + dy[i];if(nx>=0&&nx<m&&ny>=0&&ny<n && land[nx][ny]==0 && !visited[nx][ny] ){visited[nx][ny] = 1;dfs(nx,ny,++cnt);}}}
};