把迷宫看作无权图，从 S 出发做一次 BFS，首次到达 E 的步数即为最短时间；若 E 不可达则输出 oop!。
OJ: roj
题目 ID: 1256
难度:入门
标签:BFS网格最短路
创建: 2026-09-30 02:01
更新: 2026-10-05 07:12
题目描述
阿尔吉侬要从 S 走到 E，. 可走、# 为墙，每步上下左右走一格，求最少步数，不可达输出 oop!。S 和 E。样例（输入→输出）：
text
3 / 3 4 / .S.. / ###. / ..E. / 3 4 / .S.. / .E.. / .... / 3 4 / .S.. / #### / ..E. → 5 / 1 / oop!思路
把每个可达格子看成一个点，相邻可达格点连边权 1，从 S 做 BFS，首次到达 E 的层数即为最少步数；队列空仍未到 E 则输出 oop!。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47
import sys
from collections import deque
def solve() -> None:
data = sys.stdin.buffer.read().split()
it = iter(data)
T = int(next(it))
out: list[str] = []
for _ in range(T):
R = int(next(it))
C = int(next(it))
grid = [list(next(it).decode()) for _ in range(R)]
# 定位起点 S 与终点 E
for r in range(R):
for c in range(C):
if grid[r][c] == 'S':
sr, sc = r, c
elif grid[r][c] == 'E':
tr, tc = r, c
dist = [[-1] * C for _ in range(R)]
dist[sr][sc] = 0
q = deque([(sr, sc)])
while q:
r, c = q.popleft()
if (r, c) == (tr, tc):
break
d = dist[r][c] + 1
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != '#' and dist[nr][nc] == -1:
dist[nr][nc] = d
q.append((nr, nc))
out.append(str(dist[tr][tc]) if dist[tr][tc] != -1 else 'oop!')
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 07:12
* update_at: 2026-10-05 07:12
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
const int MAXN = 205;
int R, C;
char g[MAXN][MAXN]; // 地图，'S' 起点、'E' 终点、'.' 可通行、'#' 障碍
int dist_[MAXN][MAXN]; // 到达 (r,c) 的最短步数，-1 表示未访问
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
// BFS 找 S 到 E 的最少步数；不可达返回 -1
int bfs(int sr, int sc, int tr, int tc) {
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c)
dist_[r][c] = -1;
queue<pair<int,int> > q;
dist_[sr][sc] = 0;
q.push(make_pair(sr, sc));
while (!q.empty()) {
pair<int,int> cur = q.front();
q.pop();
int r = cur.first;
int c = cur.second;
if (r == tr && c == tc) return dist_[r][c];
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
if (g[nr][nc] == '#') continue;
if (dist_[nr][nc] != -1) continue;
dist_[nr][nc] = dist_[r][c] + 1;
q.push(make_pair(nr, nc));
}
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
for (int t = 0; t < T; ++t) {
cin >> R >> C;
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
cin >> g[r][c];
}
}
int sr = 0, sc = 0, tr = 0, tc = 0;
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
if (g[r][c] == 'S') { sr = r; sc = c; }
else if (g[r][c] == 'E') { tr = r; tc = c; }
}
}
int ans = bfs(sr, sc, tr, tc);
if (ans == -1) cout << "oop!";
else cout << ans;
if (t != T - 1) cout << "\n";
}
return 0;
}