E07218:献给阿尔吉侬的花束

bfs, http://cs101.openjudge.cn/practice/07218/

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

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

输入

第一行是一个正整数T（1 <= T <= 10），表示一共有T组数据。每一组数据的第一行包含了两个用空格分开的正整数R和C（2 <= R, C <= 200），表示地图是一个R×C的矩阵。接下来的R行描述了地图的具体内容，每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。

输出

对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。每组数据的输出结果占一行。

样例输入

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

样例输出

5
1
oop!

这道题的意思很清晰：标准的迷宫最短路径问题。

思路总结：

用BFS（宽度优先搜索），因为BFS可以保证第一次到达终点时就是最短路径。
每次从当前位置向上、下、左、右四个方向扩展。
遇到墙壁（#）或者越界，跳过。
记录访问过的位置，避免走回头路。
如果遍历完也没有到达终点，输出 "oop!"。

完整的代码：

python

from collections import deque

def solve_maze():
    T = int(input())
    for _ in range(T):
        R, C = map(int, input().split())
        maze = [list(input().strip()) for _ in range(R)]

        # 找起点 S
        for i in range(R):
            for j in range(C):
                if maze[i][j] == 'S':
                    start = (i, j)
                if maze[i][j] == 'E':
                    end = (i, j)

        # BFS
        queue = deque()
        visited = [[False] * C for _ in range(R)]
        queue.append((start[0], start[1], 0))  # (row, col, distance)
        visited[start[0]][start[1]] = True

        found = False

        while queue:
            x, y, dist = queue.popleft()
            if (x, y) == end:
                print(dist)
                found = True
                break

            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < R and 0 <= ny < C:
                    if not visited[nx][ny] and maze[nx][ny] != '#':
                        visited[nx][ny] = True
                        queue.append((nx, ny, dist + 1))

        if not found:
            print("oop!")

# 调用主函数
solve_maze()

简短解释一下代码逻辑：

queue 中保存 (当前x, 当前y, 走到这里用的时间/步数)。
每次扩展上下左右四个方向。
走到终点 E 时，直接输出当前走了多少步。
如果最后 queue 为空了还没到达 E，说明无法到达，输出 "oop!"。

E07218:献给阿尔吉侬的花束 ​

E07218:献给阿尔吉侬的花束