AcWing 1097. 池塘计数
原题链接
简单
作者:
过眼云烟1
,
2020-01-16 17:33:52
,
所有人可见
,
阅读 552
#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
//xy 代替pair 的first second
using namespace std;
typedef pair<int,int> PII;//重命名pair PII
const int N = 1010,M=N*N;
int n,m;
char g[N][N];//土地的矩阵
bool st[N][N];//标记访问
PII q[M];//宽搜的队列
void bfs(int sx,int sy){
int hh=0,tt=0;//队头队尾
q[0]={sx,sy};//水坑入队
st[sx][sy]==true;//访问
while(hh<=tt){//队列不空
PII t = q[hh++];//出队,进行宽搜
for(int i=t.x-1;i<=t.x+1;i++)//宽搜 8临近 用一个二维的循环挖掉中间的空
for(int j=t.y-1;j<=t.y+1;j++){
if(i==t.x&&j==t.y) continue;//挖掉中间
if(i<0||i>=n||j<0||j>=m) continue;//出去边界了
if(g[i][j]=='.'||st[i][j]) continue;//访问过或者不是水坑 的地方去掉
q[ ++ tt] = {i, j};//水坑且没有访问过 入队
st[i][j] = true;//标记访问过
}
}
}
int main(){
scanf("%d%d",&n,&m);//行数,列数
for(int i=0;i<n;i++) scanf("%s",g[i]);//%s读字符串一次可以读一行
int cnt =0;//水塘个数
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(g[i][j]=='W'&&!st[i][j])//是水塘且没有被访问过
{
bfs(i,j);
cnt++;
}
}
printf("%d",cnt);
return 0;
}