AcWing
1101. 献给阿尔吉侬的花束
bfs. 使用dist[R][C]数组记录bfs中走到每个点所需要的移动次数，-1表示该点尚未遍历。
注意，如果使用：
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
那么不能使用getchar()函数。
#include <bits/stdc++.h>
using namespace std;
int t, r, c;
const int R = 210, C = 210;
char m[R][C];
typedef pair<int, int> PII;
PII st, ed;
int dist[R][C]; // bfs中每个点所需要的移动次数，-1表示该点尚未遍历
int bfs(){
memset(dist, -1, sizeof dist);
queue<PII> q;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
q.push(st);
dist[st.first][st.second] = 0;
if(st == ed) return dist[st.first][st.second];
while(!q.empty()){
PII t = q.front();
q.pop();
for(int i = 0; i <= 3; i++){
PII tt = {t.first + dx[i], t.second + dy[i]};
if(tt.first < 1 || tt.first > r || tt.second < 1 || tt.second > c) continue;
if(m[tt.first][tt.second] == '#') continue;
if(dist[tt.first][tt.second] != -1) continue;
dist[tt.first][tt.second] = dist[t.first][t.second] + 1;
if(tt == ed) return dist[tt.first][tt.second];
q.push(tt);
}
}
return -1;
}
int main(){
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
cin >> t;
while(t --){
cin >> r >> c;
getchar();
for(int i = 1; i <= r; i++){
for(int j = 1; j <= c; j++){
m[i][j] = getchar();
if(m[i][j] == 'S') st = {i, j};
if(m[i][j] == 'E') ed = {i, j};
}
getchar();
}
int res = bfs();
if(res == -1) cout << "oop!\n";
else cout << res << '\n';
}
return 0;
}