神奇空间中房间最短传送门路径的 Python 实现

以下是使用 Python 实现的代码： ```python from collections import deque # 读取输入 n = int(input()) rooms = [] for _ in range(n): portals = list(map(int, input().split(','))) rooms.append(portals) a, b = map(int, input().split(',')) # 调整房间编号为 0 索引 a -= 1 b -= 1 # 构建图 graph = [[] for _ in range(n)] for i in range(n): for j in range(i + 1, n): # 检查两个房间是否有共同的传送门 if set(rooms[i]).intersection(set(rooms[j])): graph[i].append(j) graph[j].append(i) # BFS 搜索 visited = [False] * n queue = deque([(a, 0)]) visited[a] = True while queue: current_room, steps = queue.popleft() if current_room == b: print(steps) break for neighbor in graph[current_room]: if not visited[neighbor]: queue.append((neighbor, steps + 1)) visited[neighbor] = True else: print(-1) ``` 代码思路： 1. **输入处理**：首先读取房间数量 `n`，然后依次读取每个房间的传送门编号并存储在 `rooms` 列表中，最后读取起始房间 `a` 和目标房间 `b`。 2. **构建图**：使用二维列表 `graph` 表示房间之间的连通性。通过遍历每对房间，检查它们是否有共同的传送门，如果有则在图中添加相应的边。 3. **BFS 搜索**：使用广度优先搜索（BFS）算法来找到从起始房间到目标房间的最短路径。初始化一个队列 `queue` 用于存储待访问的房间和到达该房间所需的步数，同时使用 `visited` 列表记录每个房间是否已经被访问过。 4. **输出结果**：如果在 BFS 过程中找到了目标房间，则输出最少经过的传送门数量；如果遍历完所有可达的房间都没有找到目标房间，则输出 -1。 ######[AI问答 | 528点数解答 | 2026-02-14 20:11:28]