蓝桥杯Python编程题:给定两个房间的编号A和B,请找出从房间A到达房间B最少需要经过几个传送门。
编程实现:
在一个神奇空间里有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