A37473. （此题仅中、高级组）
填空题
困难
知识点
题目描述
（此题仅中、高级组）
题目描述：
(注.input()输入函数的括号中不允许添加任何信息)
编程实现：
在一个神奇空间里有N个房间，房间从1到N编号，每个房间可能有一个或多个传送门，每个传送门都有一个编号，如果相同编号的传送门同时出现在多个房间中，表示这些房间可以互通。
给定两个房间的编号A和B，请找出从房间A到达房间B最少需要经过几个传送门。
例如：N=3，3个房间中传送门的编号分别为：
房间1：1、4、6；
房间2：2、3、4，8；
房间3：3、6、9。
其中房间1和房间2互通，共用4号传送门；房间1和房间3互通，共用6号传送门；房间2和房间3互通，共用3号传送门；当A=1，B=2，从房间1到达房间2，共有两种路线：
路线1：从房间1通过4号传送门进入房间2，共经过1个传送门；
路线2：从房间1通过6号传送门进入房间3，再从房间3通过3号传送门进入房间2，共经过2个传送门；故从房间1到达房间2最少需要经过1个传送门。
输入描述
第一行输入一个正整数N（2≤N≤20），表示房间数量
接下来输入N行，每行包含多个正整数（1≤正整数≤100），第2行到第N+1行依次表示1到N号房间内所有传送门的编号，正整数之间以一个英文逗号隔开
最后一行输入两个正整数A和B（1≤A≤N，1≤B≤N，且A≠B），表示两个房间的编号，正整数之间以一个英文逗号隔开
输出描述
输出一个整数，表示从房间A到达房间B最少需要经过几个传送门，如果房间A不能到达房间B，则输出-1
样例输入
3
1,4,6
2,3,4,8
3,6,9
1,2
样例输出
1
参考答案
# 读取输入数据
n = int(input()) # 房间数量
rooms = [] # 记录每个房间内的传送门编号
for i in range(n):
rooms.append(list(map(int, input().split(','))))
a, b = map(int, input().split(',')) # 目标房间A和B
# 构建每个传送门所连接房间的关系表
gates = {} # {传送门编号：可到达的房间列表}
for i in range(n):
for gate in rooms[i]:
if gate not in gates:
gates[gate] = []
gates[gate].append(i)
print(gates)
# 使用BFS搜索，从房间A寻找到达房间B的最短路程
queue = [a-1] # 起点A的房间编号入队列
dist = [-1] * n # 记录每个房间到起点A的距离初始化为-1
dist[a-1] = 0 # 起点A到自身的距离为0
while queue:
u = queue.pop(0)
for gate in rooms[u]:
for v in gates[gate]:
if dist[v] == -1: # 如果该房间还没有被访问过
dist[v] = dist[u] + 1
if v == b-1: # 如果已经找到目标房间B，则立即返回最短路程
print(dist[v])
exit()
queue.append(v)
# 如果队列为空还没有找到目标房间B，则说明无法到达
print(-1)
上一题
下一题