广度优先搜索-抓住那头牛

抓住那头牛(百练习4001)：农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上
，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟
2、从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

广度优先搜索：给节点分层。起点是第0层。从起点最少需n步就能到达的点属于第n层。
依层次顺序，从小到大扩展节点。把层次低的点全部扩展出来后，才会扩展层次高的点。
可确保找到最优解，但是因扩展出来的节点较多，且多数节点都需要保存，因此
需要的存储空间较大。用队列存节点。
样例输入
5 17
样例输出
4

python 算法实现：

 1 import queue
 2 
 3 MAXN = 100000
 4 # 判重标记, visited[i] = true表示i已经扩展过
 5 visited = [0 for i in range(MAXN + 10)]
 6 
 7 
 8 class Step:
 9     # x-位置,steps-到达x所需的步数
10     x = 0
11     steps = 0
12 
13     def __init__(self, p1, p2):
14         self.x = p1
15         self.steps = p2
16 
17 
18 def main():
19     global visited, MAXN
20     N, K = map(int, input().split())
21     startLocation = Step(N, 0)
22     # 声明一个队列对象
23     q = queue.Queue()
24     # 初始位置Step对象插入队列
25     q.put(startLocation)
26     visited[N] = 1
27     while not q.empty():
28         # 获取元素后会出列
29         s = q.get()
30         # 找到目标
31         if s.x == K:
32             print("农夫最少要花%d分钟才能抓住牛" % s.steps)
33             return 0
34         else:
35             if s.x - 1 >= 0 and visited[s.x-1] == 0:
36                 q.put(Step(s.x - 1, s.steps + 1))
37                 visited[s.x - 1] = 1
38             if s.x + 1 <= MAXN and visited[s.x+1] == 0:
39                 q.put(Step(s.x + 1, s.steps + 1))
40                 visited[s.x + 1] = 1
41             if s.x * 2 <= MAXN and visited[s.x*2] == 0:
42                 q.put(Step(s.x * 2, s.steps + 1))
43                 visited[s.x * 2] = 1
44 
45     return 0
46 
47 
48 if __name__ == '__main__':
49     main()

广度优先搜索-抓住那头牛

相关推荐