题库 蓝桥杯青少组题库 题目列表 蓝桥杯Python编程题:给定两个房间的编号A和B,请找出...
问答题

蓝桥杯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

题目信息
创意编程组 第十四届 省赛 其他
-
正确率
0
评论
237
点击