04130: Saving Tang Monk
dijkstra, http://cs101.openjudge.cn/practice/04130/
《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng'en during the Ming Dynasty. In this novel, Monkey King Sun Wukong, pig Zhu Bajie and Sha Wujing, escorted Tang Monk to India to get sacred Buddhism texts.
During the journey, Tang Monk was often captured by demons. Most of demons wanted to eat Tang Monk to achieve immortality, but some female demons just wanted to marry him because he was handsome. So, fighting demons and saving Monk Tang is the major job for Sun Wukong to do.
Once, Tang Monk was captured by the demon White Bones. White Bones lived in a palace and she cuffed Tang Monk in a room. Sun Wukong managed to get into the palace. But to rescue Tang Monk, Sun Wukong might need to get some keys and kill some snakes in his way.
The palace can be described as a matrix of characters. Each character stands for a room. In the matrix, 'K' represents the original position of Sun Wukong, 'T' represents the location of Tang Monk and 'S' stands for a room with a snake in it. Please note that there are only one 'K' and one 'T', and at most five snakes in the palace. And, '.' means a clear room as well '#' means a deadly room which Sun Wukong couldn't get in.
There may be some keys of different kinds scattered in the rooms, but there is at most one key in one room. There are at most 9 kinds of keys. A room with a key in it is represented by a digit(from '1' to '9'). For example, '1' means a room with a first kind key, '2' means a room with a second kind key, '3' means a room with a third kind key... etc. To save Tang Monk, Sun Wukong must get ALL kinds of keys(in other words, at least one key for each kind).
For each step, Sun Wukong could move to the adjacent rooms(except deadly rooms) in 4 directions(north,west,south and east), and each step took him one minute. If he entered a room in which a living snake stayed, he must kill the snake. Killing a snake also took one minute. If Sun Wukong entered a room where there is a key of kind N, Sun would get that key if and only if he had already got keys of kind 1,kind 2 ... and kind N-1. In other words, Sun Wukong must get a key of kind N before he could get a key of kind N+1 (N>=1). If Sun Wukong got all keys he needed and entered the room in which Tang Monk was cuffed, the rescue mission is completed. If Sun Wukong didn't get enough keys, he still could pass through Tang Monk's room. Since Sun Wukong was a impatient monkey, he wanted to save Tang Monk as quickly as possible. Please figure out the minimum time Sun Wukong needed to rescue Tang Monk.
输入
There are several test cases.
For each case, the first line includes two integers N and M(0 < N <= 100, 0 <= M <= 9), meaning that the palace is a N * N matrix and Sun Wukong needed M kinds of keys(kind 1, kind 2, ... kind M).
Then the N*N matrix follows.
The input ends with N = 0 and M = 0.
输出
For each test case, print the minimum time (in minute) Sun Wokong needed to save Tang Monk. If it's impossible for Sun Wokong to complete the mission, print "impossible".
样例输入
3 1
K.S
##1
1#T
3 1
K#T
.S#
1#.
3 2
K#T
.S.
21.
0 0样例输出
5
impossible
8这个题目测试数据不足，新增一组,【蔡沐轩 24数学学院】提供。
样例输入2
4 2
K.S2
.#S#
.#S1
.1#T
0 0样例输出2
17样例输入3，【24-物院-吕金浩】提供
4 2
K.S2
.#S#
.#S1
.1#T
0 0样例输出3
6实现了先进行一次简单的 BFS 检查是否所有必须到达的点（唐僧以及所有钥匙）都可达，若有未达点则直接输出 "impossible"，否则再利用 Dijkstra 算法求最短救援时间。请注意以下几点：
- 我们用 BFS 预处理时，仅判断是否有路径到达目标点和各个钥匙（标号 1～m），忽略杀蛇额外耗时问题，但蛇房间并非障碍；
- 若预处理失败则直接输出 “impossible”，避免后续 Dijkstra 扩展大量状态；
- Dijkstra 部分采用状态编码，将（已取钥匙数、蛇杀记）合并成一个整数，并利用二维字典降低内存开销；
下面是完整程序，34272kB，3076ms AC。
import sys
import heapq
from collections import deque
def solve():
data = sys.stdin.read().splitlines()
if not data:
return
line_index = 0
# 四个方向：上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
results = []
while line_index < len(data):
if not data[line_index].strip():
line_index += 1
continue
parts = data[line_index].split()
line_index += 1
n = int(parts[0])
m = int(parts[1])
if n == 0 and m == 0:
break
# 读入迷宫
g = []
xs = ys = xe = ye = None
snake_index = {}
snake_count = 0
for i in range(n):
row = list(data[line_index].strip())
line_index += 1
for j, ch in enumerate(row):
if ch == 'K':
xs, ys = i, j
elif ch == 'T':
xe, ye = i, j
elif ch == 'S':
snake_index[(i, j)] = snake_count
snake_count += 1
g.append(row)
# 预处理：BFS 判断目标和所有钥匙是否可达（忽略杀蛇额外时间）
reachable = [[False]*n for _ in range(n)]
# flag[0] 表示唐僧所在房间可达，flag[1..m] 表示钥匙1..m可达
flag = [False]*(m+1)
q = deque([(xs, ys)])
reachable[xs][ys] = True
while q:
x0, y0 = q.popleft()
for dx, dy in directions:
x1, y1 = x0 + dx, y0 + dy
if not (0 <= x1 < n and 0 <= y1 < n):
continue
if g[x1][y1] == '#':
continue
if not reachable[x1][y1]:
reachable[x1][y1] = True
q.append((x1, y1))
if g[x1][y1].isdigit():
key_val = int(g[x1][y1])
if 1 <= key_val <= m:
flag[key_val] = True
elif x1 == xe and y1 == ye:
flag[0] = True
# 如果目标房间或任一必须钥匙不可达，直接输出 "impossible"
if not (flag[0] and all(flag[1:])):
results.append("impossible")
continue
# 若预处理通过，则利用 Dijkstra 求最短时间
# 状态编码：将 (已取钥匙数, 蛇杀记) 合并为一个整数
def encode(keys, smask):
return keys * (1 << snake_count) + smask
# 在每个格子上用字典记录状态编码对应的最短耗时，降低内存占用
visited = [[{} for _ in range(n)] for _ in range(n)]
init_state = encode(0, 0)
visited[xs][ys][init_state] = 0
heap = [(0, xs, ys, 0, 0)] # (耗时, x, y, keys, snake_mask)
ans = -1
while heap:
t, x, y, keys, smask = heapq.heappop(heap)
state_code = encode(keys, smask)
if visited[x][y].get(state_code, float('inf')) < t:
continue
if x == xe and y == ye and keys == m:
ans = t
break
for dx, dy in directions:
nx, ny = x + dx, y + dy
if not (0 <= nx < n and 0 <= ny < n):
continue
if g[nx][ny] == '#':
continue
nkeys = keys
nsmask = smask
nt = t + 1 # 每走一步耗时1分钟
cell = g[nx][ny]
# 若该房间有蛇且尚未杀死，则需额外1分钟，并更新蛇状态
if cell == 'S':
idx = snake_index[(nx, ny)]
if not (smask & (1 << idx)):
nt += 1
nsmask = smask | (1 << idx)
# 若该房间有钥匙且正是下一个需要的钥匙，则拾取钥匙
if cell.isdigit():
k = int(cell)
if keys < m and k == keys + 1:
nkeys = keys + 1
new_state = encode(nkeys, nsmask)
if new_state not in visited[nx][ny] or nt < visited[nx][ny][new_state]:
visited[nx][ny][new_state] = nt
heapq.heappush(heap, (nt, nx, ny, nkeys, nsmask))
results.append("impossible" if ans == -1 else str(ans))
sys.stdout.write("\n".join(results))
if __name__ == '__main__':
solve()说明
预处理 BFS
程序首先从起点 (K) 开始进行 BFS，记录每个位置是否能到达。若在扩展过程中遇到房间内的数字（钥匙）或唐僧所在的房间 (T)，就在 flag 数组中做标记。若最终 flag 中任一必需项未被标记，则说明无法救出唐僧，直接输出 "impossible"。Dijkstra 算法
仅在预处理通过时才继续用 Dijkstra 算法求解最短时间。状态采用 (x, y, keys, snake_mask) 表示，其中 keys 与 snake_mask 经过 encode() 合并编码，利用每个位置的字典记录该状态的最小耗时，从而降低内存使用。
这种改法可以在提前判断不可达情况后避免不必要的状态扩展，有助于降低内存和时间开销。
【蔡沐轩 24数学学院】：23344kB, 3254ms
from collections import deque
from heapq import *
directions=[(1,0),(0,1),(-1,0),(0,-1)]
while 1:
n,m=map(int,input().split())
if n==0 and m==0:break
g=[list(input()) for _ in range(n)]
s=[(0,0)]*5
k=0
for i in range(n):
for j in range(n):
if g[i][j]=='K':xs,ys=i,j;g[i][j]='.'
elif g[i][j]=='T':xe,ye=i,j;g[i][j]='.'
elif g[i][j]=='S':g[i][j]+=str(k);k+=1
#先进行一遍BFS，判断是否输出“impossible”，防止超时/超内存
inq=[[False]*n for _ in range(n)]
flag=[False]*(m+1)
q=deque([(xs,ys)])
inq[xs][ys]=0
while q:
x0,y0=q.popleft()
for d in directions:
x1,y1=x0+d[0],y0+d[1]
if not(0<=x1<n and 0<=y1<n) or g[x1][y1]=='#':continue
elif not inq[x1][y1]:
q.append((x1,y1))
inq[x1][y1]=True
if g[x1][y1].isdigit():flag[int(g[x1][y1])]=True
elif x1==xe and y1==ye:flag[0]=True
if not all(flag):
print("impossible")
continue
inq=[[set() for _ in range(n)] for _ in range(n)]
q=[(1,xs,ys,0)]#四个元素分别记录时间、坐标、状态
inq[xs][ys].add(0)
flag=False
# dijkstra算法
while q:
t0,x0,y0,sk0=heappop(q)
s0,k0=sk0&31,sk0>>5
if x0==xe and y0==ye and k0==m:
print(t0 - 1)
flag=True
break
for d in directions:
x1,y1=x0+d[0],y0+d[1]
if not(0<=x1<n and 0<=y1<n) or g[x1][y1]=='#':continue
elif g[x1][y1]=='.':s1,k1,t1=s0,k0,t0+1
elif g[x1][y1][0]=='S':
if (1<<int(g[x1][y1][1]))&s0:s1,k1,t1=s0,k0,t0+1
else:s1,k1,t1=s0|(1<<int(g[x1][y1][1])),k0,t0+2
elif g[x1][y1].isdigit():
if int(g[x1][y1])==k0+1:s1,k1,t1=s0,k0+1,t0+1
else:s1,k1,t1=s0,k0,t0+1
sk1=s1+(k1<<5)
if sk1 not in inq[x1][y1]:
heappush(q,(t1,x1,y1,sk1))
inq[x1][y1].add(sk1)下面程序无法AC样例2数据
使用 Dijkstra 算法
- 由于移动代价
1和2（杀蛇）不同，普通 BFS 可能导致错误的路径计算。- 使用 优先队列
heapq，保证总是扩展当前最短时间的路径。正确处理蛇的状态
snake_mask需要记录哪些蛇已被杀，以避免重复计算杀蛇时间。钥匙获取逻辑
- 必须按照 从
1到M的顺序依次获取钥匙，不能跳过。
import heapq
import sys
input = sys.stdin.read
DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 4 个方向：上、下、左、右
class Node:
def __init__(self, x, y, time, key, snake):
self.x = x # 当前位置
self.y = y # 当前位置
self.time = time # 当前耗费时间
self.key = key # 当前拿到的钥匙数量
self.snake = snake # 当前杀死的蛇的状态（用 bitmask 记录）
def __lt__(self, other):
return self.time < other.time # 优先队列需要按照时间排序（Dijkstra）
def bfs(maze, N, M):
# 记录初始位置和蛇的位置
x0, y0, snake_count = 0, 0, 0
snake_map = [[-1] * N for _ in range(N)] # 记录蛇的编号
for i in range(N):
for j in range(N):
if maze[i][j] == 'K': # 孙悟空的起点
x0, y0 = i, j
elif maze[i][j] == 'S': # 记录蛇的位置
snake_map[i][j] = snake_count
snake_count += 1
# Dijkstra 需要的优先队列
queue = []
heapq.heappush(queue, Node(x0, y0, 0, 0, 0))
# 记录访问状态：memo[x][y][key_count] 表示在 (x, y) 拥有 key_count 把钥匙的最短时间
INF = float('inf')
memo = [[[INF] * (M + 1) for _ in range(N)] for _ in range(N)]
memo[x0][y0][0] = 0 # 初始状态
while queue:
node = heapq.heappop(queue)
# 遍历四个方向
for dx, dy in DIRS:
nx, ny = node.x + dx, node.y + dy
if 0 <= nx < N and 0 <= ny < N:
cell = maze[nx][ny]
new_time = node.time + 1
new_key = node.key
new_snake_mask = node.snake
if cell == '#': # 死亡房间，不能进入
continue
elif cell == 'S': # 遇到蛇
snake_id = snake_map[nx][ny]
if (node.snake & (1 << snake_id)): # 已杀死，正常通行
pass
else: # 需要额外 1 分钟杀死蛇
new_time += 1
new_snake_mask |= (1 << snake_id)
elif cell.isdigit(): # 遇到钥匙
key_id = int(cell)
if key_id == node.key + 1: # 必须按顺序拾取
new_key += 1
elif cell == 'T' and new_key == M: # 唐僧，并且钥匙足够
return new_time
# 如果新的状态更优，则更新
if new_time < memo[nx][ny][new_key]:
memo[nx][ny][new_key] = new_time
heapq.heappush(queue, Node(nx, ny, new_time, new_key, new_snake_mask))
return "impossible" # 无法到达
# 读取输入
def main():
input_data = input().strip().split("\n")
index = 0
results = []
while index < len(input_data):
# 读取 N, M
N, M = map(int, input_data[index].split())
if N == 0 and M == 0:
break
# 读取宫殿地图
maze = [list(input_data[i]) for i in range(index + 1, index + 1 + N)]
results.append(str(bfs(maze, N, M)))
# 更新索引
index += N + 1
# 输出结果
print("\n".join(results))
if __name__ == "__main__":
main()复杂度分析
- 时间复杂度：O(N^2 * 2^M)
N^2是宫殿的格子数2^M是钥匙状态的可能性- 由于
heapq优化，每个状态扩展操作是O(log (N^2 * 2^M))- 空间复杂度：O(N^2 * 2^M)
- 主要存储
memo[x][y][key_count]，每个(x, y)状态最多M+1种钥匙状态
下面程序无法AC样例2数据
python# 2300011335 邓锦文 import heapq import sys input = sys.stdin.readline class Node: def __init__(self, x, y, time, key, snake): self.x = x self.y = y self.time = time self.key = key self.snake = snake # 用二进制位表示经过的蛇 def __lt__(self, other): return self.time < other.time def bfs(maze, n, m): x0, y0, count = 0, 0, 0 snakes = [[0] * n for _ in range(n)] for i in range(n): for j in range(n): if maze[i][j] == 'K': x0, y0 = i, j if maze[i][j] == 'S': snakes[i][j] = count count += 1 dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)] inf = float('inf') memo = [[[inf] * (m + 1) for _ in range(n)] for _ in range(n)] queue = [] heapq.heappush(queue, Node(x0, y0, 0, 0, 0)) memo[x0][y0][0] = 0 while queue: node = heapq.heappop(queue) for dx, dy in dirs: nx, ny = node.x + dx, node.y + dy if 0 <= nx < n and 0 <= ny < n: if maze[nx][ny] == '#': continue elif maze[nx][ny] == 'S': if node.snake & (1 << snakes[nx][ny]): if node.time + 1 < memo[nx][ny][node.key]: memo[nx][ny][node.key] = node.time + 1 heapq.heappush(queue, Node(nx, ny, node.time + 1, node.key, node.snake)) else: if node.time + 2 < memo[nx][ny][node.key]: memo[nx][ny][node.key] = node.time + 2 # snake：表示经过蛇的情况，这里使用位运算 # 将当前位置的蛇加入到 node.snake 中，表示经过了当前位置的蛇。 heapq.heappush(queue, Node(nx, ny, node.time + 2, node.key, node.snake | (1 << snakes[nx][ny]))) elif maze[nx][ny].isdigit(): if int(maze[nx][ny]) == node.key + 1: if node.time + 1 < memo[nx][ny][node.key + 1]: memo[nx][ny][node.key + 1] = node.time + 1 heapq.heappush(queue, Node(nx, ny, node.time + 1, node.key + 1, node.snake)) else: if node.time + 1 < memo[nx][ny][node.key]: memo[nx][ny][node.key] = node.time + 1 heapq.heappush(queue, Node(nx, ny, node.time + 1, node.key, node.snake)) elif maze[nx][ny] == 'T' and node.key == m: return node.time + 1 else: if node.time + 1 < memo[nx][ny][node.key]: memo[nx][ny][node.key] = node.time + 1 heapq.heappush(queue, Node(nx, ny, node.time + 1, node.key, node.snake)) return 'impossible' result = [] while True: n, m = map(int, input().split()) if n == m == 0: break maze = [list(input()) for _ in range(n)] result.append(bfs(maze, n, m)) for tmp in result: print(tmp)