迷宫用一个 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!
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int N = 210;
char mp[N][N];
int dist[N][N] = {-1};
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int t;
int r,c;
int flag = 0;
struct node{
int x,y;
};
node st,en;
queue<node> q;
int bfs(int xx,int yy)
{
_****一定要有清空队列不然队列里仍有上次的结果,或者把队列定义在bfs里****_
//queue<node> q;将队列定义在这里!!!!
while (!q.empty()) q.pop(); // 清空队列!!!!!!!
q.push({xx,yy});
dist[xx][yy] = 0;
while(!q.empty()){
node temp = q.front();
q.pop();
for(int i = 0;i < 4; i ++){
int nx = temp.x + dx[i];
int ny = temp.y + dy[i];
if(nx > r || nx < 1 || ny < 1 || ny > c) continue;
if(mp[nx][ny] == '#') continue;
if(dist[nx][ny] != -1) continue;
dist[nx][ny] = dist[temp.x][temp.y] + 1;
if(mp[nx][ny] == 'E'){
// printf("***\n");
flag = 1;
return dist[nx][ny];
}
q.push({nx,ny});
}
}
return -1;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&r,&c);
flag = 0;
memset(mp,'#',sizeof(mp));
memset(dist,-1,sizeof(dist));
for(int i = 1;i <= r; i ++){
for(int j = 1; j <= c; j ++){
cin>>mp[i][j];
// cout<<mp[i][j]<<" ";
if(mp[i][j] == 'S'){
st.x = i;
st.y = j;
//printf("%d %d\n",i,j);
}
}
}
int ans = bfs(st.x, st.y);
if(flag == 1)
printf("%d\n",ans);
else
cout<<"oop!"<<endl;
}
return 0;
}