有没有更简便的解法,不是很懂defaultdict, deque
时间: 2023-12-08 18:04:17 浏览: 67
除了使用 defaultdict 和 deque,还可以使用普通的字典和列表来实现广度优先搜索算法。
下面是使用普通的字典和列表来实现广度优先搜索算法的 Python 代码:
```python
# 读入输入数据
n = int(input())
rooms = {}
for i in range(1, n + 1):
rooms[i] = list(map(int, input().split(',')))
a, b = map(int, input().split(','))
# 广度优先搜索
queue = [a] # 创建队列,将起点A添加进队列
visited = set([a]) # 创建集合,将起点A添加进集合
dist = {a: 0} # 创建距离字典,将起点A的距离初始化为0
while queue: # 当队列不为空时
curr = queue.pop(0) # 取出队列中的第一个元素,表示当前所在的房间
if curr == b: # 如果当前房间是终点B,返回该房间的距离
print(dist[curr])
break
for door in rooms[curr]: # 遍历当前房间中的传送门编号
if door not in visited: # 如果该传送门通往的房间不在集合中
visited.add(door) # 将该房间添加进集合中
dist[door] = dist[curr] + 1 # 将其距离设置为当前房间的距离加1
queue.append(door) # 将该房间添加进队列中
else: # 如果遍历完所有可以到达的房间后还没有找到终点B,则返回-1
print(-1)
```
这个代码没有使用 defaultdict 和 deque,只用了普通的字典和列表,更加简洁易懂。但是,这个代码的时间复杂度比使用 deque 的代码要高,因为在列表中插入和删除元素的时间复杂度是 O(n),而使用 deque 可以将时间复杂度降为 O(1)。
希望这个代码可以帮助到您,如有其他问题,请随时提问!
阅读全文