M29954: 逃离紫罗兰监狱

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

作为一名强大的肯瑞托大法师，你在巡视达拉然的紫罗兰监狱时，牢房突然失控，你被困在了一片禁魔区域中！这片区域可以被视为一个 R x C 的网格。

网格地形如下：

. : 开放的走廊，可以安全移动。
# : 闪烁的魔法屏障，阻挡了你的去路。
S : 你被困的初始位置。
E : 区域的紧急传送出口。

幸运的是，你对空间魔法的精通使你依然能勉强使用招牌技能——“闪现术”。由于禁魔区域的干扰，你的法力只够支撑你施展最多 K 次闪现术，且你的闪现术无法直接抵达魔法屏障另一边的位置，只能让你暂时留存于屏障内。当然，你在屏障中时可以正常移动到开放的走廊，如果有足够的法力也可以继续使用闪现术移动到其他相邻魔法屏障内。

你现在想尽快地逃离紫罗兰监狱，于是你开始计算从 S 点抵达出口 E 所需要的最少行动次数。无论是正常移动到相邻（上、下、左、右）的走廊，还是使用一次闪现术穿过屏障，都算作一次行动。

**移动规则补充说明：

你的每一次行动，都是从当前所在的格子，向其上、下、左、右四个方向中的一个相邻格子**进行移动。每次移动，无论是否使用闪现术，都记为 1 次行动。

是否消耗法力（或”闪现术次数”）仅由你的目标格子类型决定：

如果你的目标格子是走廊 .：不消耗闪现术次数；

如果你的目标格子是屏障 #：你必须消耗 1 次闪现术次数才能完成移动。（如果你没有剩余闪现术次数，则此路不通）。

输入

第一行包含三个整数 R, C, K (1 <= R, C <= 100, 0 <= K <= 10)。

接下来 R 行，每行 C 个字符，描述监狱区域的布局。

输出

输出一个整数，代表最短行动次数。如果无法到达，输出 -1。

样例输入

5 5 1
S.###
.#.#.
.#.##
..#.#
###.E

样例输出

提示

tag: bfs

来源

2025 TA-lxy

把魔力当作一维，visisted是三维数组。

python

from collections import deque

R, C, K = map(int, input().split())
grid = [list(input().strip()) for _ in range(R)]

# 找到起点 S 和终点 E
for i in range(R):
    for j in range(C):
        if grid[i][j] == 'S':
            sr, sc = i, j
        elif grid[i][j] == 'E':
            er, ec = i, j

# BFS
q = deque()
q.append((sr, sc, 0, 0))  # (行, 列, 已使用闪现次数, 步数)
visited = [[[False] * (K + 1) for _ in range(C)] for _ in range(R)]
visited[sr][sc][0] = True

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while q:
    r, c, used, steps = q.popleft()
    if (r, c) == (er, ec):
        print(steps)
        break

    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C:
            cell = grid[nr][nc]
            if cell != '#' and not visited[nr][nc][used]:
                visited[nr][nc][used] = True
                q.append((nr, nc, used, steps + 1))
            elif cell == '#' and used < K and not visited[nr][nc][used + 1]:
                visited[nr][nc][used + 1] = True
                q.append((nr, nc, used + 1, steps + 1))
else:
    print(-1)

M29954: 逃离紫罗兰监狱 ​

M29954: 逃离紫罗兰监狱