AcWing 1100. 抓住那头牛 简单BFS应用
原题链接
简单
作者:
皓首不倦
,
2020-08-01 16:26:45
,
所有人可见
,
阅读 505
'''
简单BFS找最短路长度
'''
from collections import deque
m, n = map(int, input().split())
def bfs(m, n):
que = deque()
que.append(m)
visited = {m}
step = 0
while len(que) > 0:
node_num = len(que)
for _ in range(node_num):
cur = que.popleft()
if cur-1 >= 0 and cur-1 not in visited:
if cur-1 == n:
return step+1
visited.add(cur-1)
que.append(cur-1)
if cur < n:
if cur+1 not in visited:
if cur+1 == n:
return step+1
visited.add(cur + 1)
que.append(cur + 1)
if cur * 2 not in visited:
if cur*2 == n:
return step+1
visited.add(cur * 2)
que.append(cur * 2)
step += 1
return -1
print(bfs(m, n))