4114: 传送门
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
编程实现：
在一个神奇空间里有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(","))
def bfs(start,target):
queue.insert(0,(start,0))
while queue:
room,steps=queue.pop()
if room==target:
return steps
for num in rooms[room]:
for t in range(len(rooms)):
if t!=room and num in rooms[t]:
queue.insert(0,(t,steps+1))
return -1
queue=[]
ans=bfs(a-1,b-1)
print(ans)