有一天我做了一个梦,梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯,而且第 i 层楼(1≤i≤N)上有一个数字 Ki\n(0≤Ki≤N)。电梯只有四个按钮:开,关,上,下。上下的层数等于当前楼层上的那个数字。当然,如果不能满足要求,相应的按钮就会失灵。例如: 3,3,1,2,5 代表了 Ki\n(K1=3,K2=3,……),从 1楼开始。在 1楼,按“上”可以到 4 楼,按“下”是不起作用的,因为没有 −2 楼。那么,从 A 楼 到 B 楼至少要按几次按钮呢?\n\n1≤N≤200,1≤A,B≤N,0≤Ki≤N\n\n输入格式:\n有多组输入,用0分隔每组数据,每组第一行表示 N, A, B\n第二行为 N 个用空格隔开的非负整数,表示 Ki,第三行0表示该组结束\n\n输出格式:\n最少按键次数,若无法到达,则输出 -1
时间: 2023-04-11 11:02:31 浏览: 86
这是一道经典的图论问题,可以使用广度优先搜索(BFS)来解决。我们可以将每一层楼看作图中的一个节点,如果两个节点之间可以通过电梯到达,则在它们之间连一条边。然后,我们可以从起点 A 开始进行 BFS,直到找到终点 B 或者无法到达。
在 BFS 过程中,我们需要记录每个节点的层数和当前所在的楼层。对于每个节点,我们可以按照上下按钮的顺序依次尝试,如果能够到达一个新的节点,则将其加入队列中,并更新其层数和当前所在的楼层。
如果 BFS 结束后仍然没有找到终点 B,则说明无法到达,输出 -1。
下面是完整的代码实现:
```python
from collections import deque
class Czhidao:
def __init__(self):
self.graph = []
self.visited = []
self.n = 0
def bfs(self, start, end):
queue = deque([(start, 0, start)])
self.visited[start] = True
while queue:
node, level, floor = queue.popleft()
if node == end:
return level
for delta in [-1, 1]:
next_floor = floor + delta * self.graph[node]
if 1 <= next_floor <= self.n and not self.visited[next_floor]:
self.visited[next_floor] = True
queue.append((next_floor, level + 1, next_floor))
return -1
def run(self):
while True:
self.n, start, end = map(int, input().split())
if self.n == 0:
break
self.graph = [0] + list(map(int, input().split()))
self.visited = [False] * (self.n + 1)
result = self.bfs(start, end)
print(result)
if __name__ == '__main__':
czhidao = Czhidao()
czhidao.run()
```
注意,这里我们使用了一个类来封装整个程序,方便管理和维护。在 `__init__` 方法中,我们初始化了图和 visited 数组。在 `bfs` 方法中,我们使用队列来实现 BFS,同时记录每个节点的层数和当前所在的楼层。在 `run` 方法中,我们读入输入数据,并调用 `bfs` 方法求解。