题目描述

blablabla

样例

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
 int r,c,t;
 const int N=210;
 typedef pair<int,int>PII;
char g[N][N];
int dist[N][N];/*存储每个位置到起点的距离*/

int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

int bfs(PII start,PII end){
    queue<PII> q;/*队列的定义一般在bfs里面，
    只循环一次的话可以用全局变量，但是主函数里引用bfs函数t次，
    如果队列定义为全局变量的话队列会有残余   队列q里的元素代表点的位置坐标*/
 memset(dist,-1,sizeof dist);
 dist[start.x][start.y]=0;/*起点距离为0*/
 q.push(start);/*起点入队*/

 while(q.size()){
     auto s=q.front();/*取出队首元素*/
     q.pop();
     for(int i=0;i<4;i++){/*检查四个方向，三种情况直接跳过*/
         int a=s.x+dx[i],b=s.y+dy[i];
         if(a<0||a>=r||b<0||b>=c) continue; /*出界*/
         if(g[a][b]=='#') continue;/*遇到障碍物*/
         if(dist[a][b]!=-1) continue;/*已经访问过*/
         dist[a][b]=dist[s.x][s.y]+1;
         if(end==make_pair(a,b)) return dist[a][b];
         q.push({a,b});
     }
 }
 return -1;
}
int main(){

    cin>>t;
    while(t--){
        cin>>r>>c;
        for(int i=0;i<r;i++){/*这里只需要一个for循环即可，因为题目中给出的输入的字符之间没有空格，这里就和string输入时类似，但g不能是string，因为后续需要确定是S，E的位置*/
            scanf("%s",g[i]);
        }
        PII start,end;
        for(int i=0;i<r;i++){
            for(int j=0;j<c;j++){
                if(g[i][j]=='S') start={i,j};
               else if(g[i][j]=='E') end={i,j};
            }
        }
        int distance=bfs(start,end);
        if(distance==-1) cout<<"oop!"<<endl;
        else cout<<distance<<endl;
    }
    return 0;
}