题目描述

阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。

今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。

现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。

迷宫用一个 R×C的字符矩阵来表示。字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。

阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。

输入格式
第一行是一个正整数 T，表示一共有 T组数据。
每一组数据的第一行包含了两个用空格分开的正整数 R和 C，表示地图是一个 R×C的矩阵。
接下来的 R行描述了地图的具体内容，每一行包含了 C个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。

输出格式
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。
若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。
每组数据的输出结果占一行。

数据范围
1<T≤10,
2≤R,C≤200

样例

输入样例：

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

输出样例：

5
1
oop!

dfs:1 2 5 6 3 7 9 10 8 4
bfs:1 2 3 4 5 6 7 8 9 10


用mapp[][]数组接收地图
用dis[][]存储每个点的路径长度

起点入队
如果队列非空，一直执行下面语句：
队头出队。
遍历队头的上下左右四个方向：如果是 ‘#’ 就跳过不入队，如果dis的值不等于-1说明走过，不入队，如果超过了边界不入队，其他是‘.’且没有走过将该位置入队，该点对应的dis值更新为队头的dis + 1，如果是 ‘E’,走到了终点，输出该点对应的 dis 值。因为广搜是一层一层的，所以谁先到end谁的步数就是最小的。

如果队列为空，还没有找到终点，则无法到达，输出 oop!。

找最小步数的路径用bfs，一条路径去搜用dfs

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int T;
int r,c;
int dis[205][205];
char mapp[205][205]; 
int fx[5]={0,0,1,-1},fy[5]={1,-1,0,0};
int bfs(PII start,PII end){
    memset(dis,-1,sizeof(dis));
    queue<PII> q;
    dis[start.x][start.y]=0;
    q.push(start);
    while(!q.empty()){
        PII t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int a=t.x+fx[i];
            int b=t.y+fy[i];
            if(a<0||a>=r||b<0||b>=c) continue;
            if(dis[a][b]!=-1) continue;//之前已经走过了 
            if(mapp[a][b]=='#') continue;//有障碍物
            dis[a][b]=dis[t.x][t.y]+1;//路经长度加一 
            if(end==make_pair(a,b)) return dis[a][b];//到终点了,返回终点对应的路径长度 
            q.push({a,b});
        }
    }
    return -1;
}
int main(int argc, char** argv) {
scanf("%d",&T);
while(T--){
    cin>>r>>c;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin>>mapp[i][j];
        }
    }
    PII start,end;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(mapp[i][j]=='S') start={i,j};
            if(mapp[i][j]=='E') end={i,j};
        }
    }
    int distance=bfs(start,end);
    if(distance==-1) printf("opp!\n");
    else printf("%d\n",distance);
}
 return 0;
}