1101. 献给阿尔吉侬的花束

1101. 献给阿尔吉侬的花束

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

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

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

迷宫用一个 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 <queue>
#include <cstring> 

using namespace std;

typedef pair<int, int> P;

int r,c;
char mp[205][205];
int dist[205][205];
int sx, sy;

bool check(int x, int y){
	return x < 0 || x >= r || y < 0 || y >= c || mp[x][y] == '#'; 
}

int bfs(){
	memset(dist, 0, sizeof dist);
	queue<P> que;
	que.push(P(sx, sy));
	dist[sx][sy] = 0;
	while(que.size()){
		P top = que.front();
		que.pop();
		int dx[4] = {0 , 0, 1, -1}, dy[4] = {1, -1, 0, 0};
		for(int i = 0; i < 4; i++){
			int tx = top.first + dx[i], ty = top.second + dy[i];
			if(check(tx, ty))continue;
			if(mp[tx][ty] == 'E'){
				return dist[top.first][top.second]+1;
			}
			que.push(P(tx, ty));
			dist[tx][ty] = dist[top.first][top.second] + 1;
			mp[tx][ty] = '#';                    // 如果把标记走过的点放在从队列中取出的时候进行标记，会超时 
		}
	}
	return -1;
}

int main(){
	int t;
	cin>>t;
	while(t--){
		scanf("%d%d", &r, &c);
		for(int i = 0; i < r; i++){
			scanf("%s", mp[i]);
		}
		for(int i = 0; i < r; i++)
		for(int j = 0; j < c; j++){
			if(mp[i][j] == 'S'){
				sx = i, sy = j;
			}
		}
		mp[sx][sy] = '#';
		int ans = bfs();
		if(ans == -1){
			cout<<"oop!"<<endl;
		}else{
			cout<<ans<<endl;
		}
	}
	
}