目录
题目描述
有一些小草和一些湖泊，现在，我们把它们通一看成水池，假设有一张某处的地图，这个地图上仅标识了此处是否是水池，现在，你的任务来了，请用算出该地图*有几个水池。
‘#’表示湖泊
‘*’表示小草
输入
单组数据输入
第一行两个数n和m，地图的行数n(0<m<100)与列数m(0<n<100)
然后，输入接下来的n行每行输入m个数，表示此处有水还是没水（#表示此处是水池，*表示此处是小草）
输出
输出该地图中水池的个数。
要注意，每个水池的旁边（上下左右四个位置）如果还是水池的话的话，它们可以看做是同一个水池。
输入样例
输出样例
3
代码实现
#include<iostream>
using namespace std;
const int MAX = 1e2+5;
char map[MAX][MAX];
int n,m;
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
void dfs(int x,int y)
{
for(int i = 0; i < 4;++i)
{
int xx = x + X[i];
int yy = y + Y[i];
if(xx>=0&&xx<n&&yy>=0&&yy<m&&map[xx][yy]=='#')
{
map[xx][yy] = '*';
dfs(xx,yy);
}
}
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
cin >> map[i][j];
int ans = 0;
for(int i = 0;i < n;++i)
for(int j = 0;j < m;++j)
{
if(map[i][j]=='#')
{
dfs(i,j);
ans++;
}
}
cout << ans<<endl;
return 0;
}
思考
分别从四个方向搜索，如果是水池，则将它划分成水池的同一类，将它赋值地面