AcWing 1101. 献给阿尔吉侬的花束---Y总bfs模板
原题链接
简单
作者:
LeeDV
,
2024-04-09 14:41:41
,
所有人可见
,
阅读 1
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=210;
char g[N][N];
int d[N][N];
int t,r,c;
int bx,by,ex,ey;
PII q[N*N];
int bfs()
{
int hh=0,tt=0;
q[0]={bx,by};
// cout<<"q[0]: "<<q[0].first<<" "<<q[0].second<<endl;
memset(d,-1,sizeof(d));
d[bx][by]=0;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<4;i++)
{
int x=t.first+dx[i];
int y=t.second+dy[i];
if(x>=1&&x<=r&&y>=1&&y<=c&&(g[x][y]=='.'||g[x][y]=='E')&&d[x][y]==-1)
{
// cout<<x<<" "<<y<<endl;
d[x][y]=d[t.first][t.second]+1;
q[++tt]={x,y};
if(x==ex&&y==ey)
{
// cout<<d[ex][ey]<<endl;
return d[ex][ey];
}
}
}
}
// return d[ex][ey];
return -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
memset(g,'#',sizeof(g));
cin>>r>>c;
// cout<<r<<c<<endl;
for(int i=1;i<=r;i++)
{
// cout<<1<<endl;
for(int j=1;j<=c;j++)
{ cin>>g[i][j];
if(g[i][j]=='S')
{bx=i,by=j;//开头
// cout<<bx<<" "<<by<<endl;
}
if(g[i][j]=='E')
{ex=i,ey=j;//结尾
// cout<<ex<<" "<<ey<<endl;
}
}
}
int tmp=bfs();
if(tmp==-1)
{
cout<<"oop!"<<endl;
}else cout<<tmp<<endl;
}
return 0;
}