题目描述
Code
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=205;
char g[N][N];
int sx,sy,tx,ty;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
struct Node{
int x,y;
int dis;
};
int bfs(){
queue<Node> q;
Node st={sx,sy,0};
q.push(st);
g[sx][sy]='#';
while(q.size()){
auto u=q.front();
q.pop();
if(u.x==tx&&u.y==ty){
return u.dis;
}
for(int i=0;i<4;++i){
int fx=u.x+dx[i];
int fy=u.y+dy[i];
Node t={fx,fy,0};
if(fx>=1&&fx<=n&&fy>=1&&fy<=m&&g[fx][fy]!='#'){
g[fx][fy]='#';
t.dis=u.dis+1;
q.push(t);
}
}
}
return -1;
}
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
cin>>g[i][j];
if(g[i][j]=='S')sx=i,sy=j;
if(g[i][j]=='E')tx=i,ty=j;
}
int res=bfs();
if(res!=-1)cout<<res<<endl;
else cout<<"oop!"<<endl;
}
return 0;
}
bfs模板题,卡了输出有点费解。。