献给阿尔吉侬的花束

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 
 7 const int N=205;
 8 char a[N][N];
 9 int r,c,b[N][N],t[]={1,0,-1,0,0,1,0,-1};
10 queue<int> q;
11 
12 void bfs(){
13     while(!q.empty()){
14         int x=q.front();
15         q.pop();
16         int y=q.front();
17         q.pop();
18         for(int i=0;i<4;i++){
19             int nx=x+t[i],ny=y+t[i+4];
20             if(nx>0&&nx<=r&&ny>0&&ny<=c&&(a[nx][ny]=='.'||a[nx][ny]=='E')&&(!b[nx][ny]||b[nx][ny]>b[x][y]+1)){
21                 q.push(nx),q.push(ny);
22                 b[nx][ny]=b[x][y]+1;
23             }
24         }
25     }
26 }
27 int main(){
28     int x1,y1,x2,y2,n;
29     char cc;
30     cin>>n;
31     while(n--){
32         cin>>r>>c;
33         getchar();
34         for(int i=1;i<=r;i++){
35             for(int j=1;j<=c;j++){
36                 scanf("%c",&cc);
37                 if(cc=='S'){
38                     x1=i,y1=j;
39                 }else if(cc=='E'){
40                     x2=i,y2=j;
41                 }
42                 a[i][j]=cc;
43             }
44             getchar();
45         }
46         memset(b,0,sizeof(b));
47         q.push(x1),q.push(y1);
48         bfs();
49         if(b[x2][y2])printf("%d\n",b[x2][y2]);
50         else printf("oop!\n");
51     }
52     return 0;
53 }