AcWing 1113. 红与黑
原题链接
简单
作者:
hai阿卢
,
2021-02-04 18:24:49
,
所有人可见
,
阅读 206
红与黑 BFS
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=25;
char a[N][N];
int n,m,ox,oy;
bool s[N][N];//通过s标记位置是否走过
typedef pair<int,int> PII;
queue<PII>p;
int bfs()
{
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
p.push({ox,oy});
s[ox][oy]=true;
int cnt=1;
//如果队列空则循环截止
while(!p.empty())
{
auto it=p.front();//取队头元素
p.pop();//弹出队头
for(int i=0;i<4;i++)
{
int x=it.first+dx[i];
int y=it.second+dy[i];
//如果xy合法则入队,并标记
if(x<m&&x>=0&&y<n&&y>=0&&!s[x][y]&&a[x][y]=='.')
{
p.push({x,y});
cnt++;
s[x][y]=true;
}
}
}
return cnt;
}
int main()
{
while(cin>>n>>m,n&&m)
{
//清除上次操作的残留
memset(a,0,sizeof(a));
for(int i=0;i<=N;i++)
for(int j=0;j<=N;j++)
s[i][j]=false;
//输入数据
for(int i=0;i<m;i++) cin>>a[i];
//寻找起点
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(a[i][j]=='@') ox=i,oy=j;
//输出结果
cout<<bfs()<<endl;
}
return 0;
}