刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

题目描述：

(注.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

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythonN = int(input())rooms = [list(map(int, input().split(','))) for _ in range(N)]A, B = map(int, input().split(','))# 使用字典来记录每个房间能够到达的房间reachable = i: [] for i in range(1, N+1)# 深度优先搜索def dfs(room, path):for door in rooms[room-1]:if door not in path:path.append(door)if door == B:return len(path)for i in range(1, N+1):if door in rooms[i-1]:if i not in reachable[room]:reachable[room].append(i)if i not in reachable[door]:reachable[door].append(i)path.pop()min_steps = min(dfs(i, path) for i in reachable[room] if i != room)if min_steps != float('inf'):return min_steps + 1return float('inf')min_steps = dfs(A, [])if min_steps == float('inf'):print(-1)else:print(min_steps)```

解析：

【喵呜刷题小喵解析】：
这个问题可以通过深度优先搜索（DFS）来解决。首先，我们构建一个字典 `reachable` 来记录每个房间能够到达的房间。然后，我们进行DFS遍历，从房间A开始，每经过一个传送门，我们将其添加到路径中，并检查是否到达了房间B。如果到达了，我们返回路径的长度，即经过的传送门数量。如果未到达，我们遍历所有与当前房间和当前传送门相连的房间，并将它们添加到 `reachable` 字典中。然后，我们递归地调用DFS，从可达的房间开始，直到找到到达房间B的最短路径。如果DFS无法到达房间B，则返回无穷大。最后，我们检查 `min_steps` 是否为无穷大，如果是，则输出-1，否则输出 `min_steps`。

注意，由于题目要求输入函数的括号中不允许添加任何信息，因此我们在代码中直接使用了 `input()` 函数来获取输入。
创作类型：
原创

本文链接：题目描述： (注.input()输入函数的括号中不允许添加任何信息) 编程实现： 在一个神奇空间里有

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share