E07218 献给阿尔吉侬的花束

思路：bfs 求 01 最短路即可。

• 注意有多组数据，记得清空队列！

#include <iostream>
#include <queue>

using namespace std;

struct Node {
	int x;
	int y;
	
	Node(int _x, int _y) : x(_x), y(_y) {}
};

int dis[200][200];
string mp[200];
queue<Node> q;

void init(int r, int c){
	while (!q.empty()) q.pop();
	for (int i = 0; i < r; i++){
		for (int j = 0; j < c; j++){
			dis[i][j] = 0x7fffffff;
		}
	}
}

void find(int r, int c, int &x, int &y, char ch){
	for (int i = 0; i < r; i++){
		for (int j = 0; j < c; j++){
			if (mp[i][j] == ch){
				x = i;
				y = j;
				return;
			}
		}
	}
}

int main(){
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++){
		int r, c, sx, sy;
		bool flag = false;
		cin >> r >> c;
		init(r, c);
		for (int j = 0; j < r; j++){
			cin >> mp[j];
		}
		find(r, c, sx, sy, 'S');
		dis[sx][sy] = 0;
		q.push(Node(sx, sy));
		while (!q.empty()){
			Node cur = q.front();
			q.pop();
			if (mp[cur.x][cur.y] == 'E'){
				flag = true;
				cout << dis[cur.x][cur.y] << endl;
				break;
			}
			for (int j : {-1, 1}){
				int nx = cur.x + j;
				if (nx >= 0 && nx < r && mp[nx][cur.y] != '#' && dis[nx][cur.y] == 0x7fffffff){
					dis[nx][cur.y] = dis[cur.x][cur.y] + 1;
					q.push(Node(nx, cur.y));
				}
			}
			for (int j : {-1, 1}){
				int ny = cur.y + j;
				if (ny >= 0 && ny < c && mp[cur.x][ny] != '#' && dis[cur.x][ny] == 0x7fffffff){
					dis[cur.x][ny] = dis[cur.x][cur.y] + 1;
					q.push(Node(cur.x, ny));
				}
			}
		}
		if (!flag) cout << "oop!" << endl;
	}
	return 0;
}