题目描述

阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。

迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置，字符E表示奶酪所在的位置，字符#表示墙壁，字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 225;
int n, m;
char g[N][N];   // 迷宫
bool st[N][N];  // 标记
int dir[4][2] = { -1,0,0,1,1,0,0,-1 };  // 方向数组
struct node {
	int x, y, step;
	node(int x, int y, int step) : x(x), y(y), step(step){}
};
void push(queue<node> &q, int x, int y, int step) {
	q.emplace(x, y, step);
	st[x][y] = true;
}
bool check(int x, int y) {
	return x >= 0 && x < n&& y >= 0 && y < m && (g[x][y] == '.' || g[x][y] == 'E') && !st[x][y];
}
int bfs(int sx, int sy, int ex, int ey) {
	queue<node> q;
	push(q, sx, sy, 0);
	while (q.size()) {
		node t = q.front();
		if (t.x == ex && t.y == ey) return t.step;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = t.x + dir[i][0], ny = t.y + dir[i][1];
			if (check(nx, ny)) push(q, nx, ny, t.step + 1);
		}
	}
	return -1;
}
int main() {
	int t;
	cin >> t;
	while (t--) {
		int sx, sy, ex, ey;
		cin >> n >> m;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				cin >> g[i][j];
				if (g[i][j] == 'S') sx = i, sy = j;
				else if (g[i][j] == 'E') ex = i, ey = j;
			}
		memset(st, false, sizeof st);  //重置st
		int s = bfs(sx, sy, ex, ey);
		if (s == -1) cout << "oop!" << endl;  //无法到达
		else cout << s << endl;
	}
	return 0;
}