我们拒绝使用bfs!
2024-04-09 22:41:51
发布于:广东
12阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int xcor[]={1,1,1,0,0,-1,-1,-1};//x坐标变动数组
int ycor[]={1,0,-1,1,-1,1,0,-1};//y坐标变动数组
char a[1145][1145];//输入数组
void dfs(int x,int y)//深度优先搜索
{
if(x<1||x>n||y<1||y>m||a[x][y]=='.') return ;//越界/已经被统计/没有水
a[x][y]='.';//标记为干燥,说明被统计过了
for(int i=0;i<8;i++)
{
int nx=x+xcor[i],ny=y+ycor[i];
dfs(nx,ny);
}
return ;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)//输入
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)//遍历数组,找出有水的地方
{
for(int j=1;j<=m;j++)
{
if(a[i][j]=='.') continue;//如果已经是干燥,跳过
else
{
dfs(i,j);//搜索
cnt++;//增加1
}
}
}
cout<<cnt;//输出
}
这里空空如也
有帮助,赞一个