AcWing 1101. 献给阿尔吉侬的花束
原题链接
简单
作者:
吴鑫
,
2021-02-03 10:07:28
,
所有人可见
,
阅读 280
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
char ch[510][510];
int d[510][510];
int n,m,T;
int bfs(int x,int y){
int xx[]={-1,0,1,0},yy[]={0,1,0,-1};
memset(d,-1,sizeof d);
queue<PII> q;
q.push({x,y});
d[x][y]=0;
while(q.size()){
auto t=q.front();
q.pop();
for(int i=0;i<4;i++){
int fx=t.first+xx[i],fy=t.second+yy[i];
if(fx<0||fy<0||fx==n||fy==m||d[fx][fy]!=-1||ch[fx][fy]=='#') continue;
d[fx][fy]=d[t.first][t.second]+1;
if(ch[fx][fy]=='E') return d[fx][fy];
q.push({fx,fy});
}
}
return -1;
}
int main(){
cin>>T;
while(T--){
int x,y;
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
cin>>ch[i][j];
if(ch[i][j]=='S') x=i,y=j;
}
int k=bfs(x,y);
if(k==-1) puts("oop!");
else printf("%d\n",k);
}
return 0;
}