我是靠谱客的博主 含糊棒球,这篇文章主要介绍抓牛(poj4001)BFS,现在分享给大家,希望可以做个参考。

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.

  • Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
  • Teleporting: FJ can move from any point X to the point 2 × X in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?

Input

Line 1: Two space-separated integers: N and K

Output

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

Sample Input

5 17

Sample Output

4

解题思路:

复制代码
1
2
3
建立队列,通过bfs找寻最优解

code:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; struct node { int x,c; }pos[200000];//该点的坐标和走过的步数 int n,k; queue<node>q;//队列 bool vis[200000];//判断是否走过该点 int bfs() { int p,cnt; while(!q.empty()) { p=q.front().x; cnt=q.front().c; q.pop(); if(p==k)return cnt; if(!vis[p-1]&&p>0) { vis[p-1]=1; pos[p-1].c=cnt+1; pos[p-1].x=p-1; q.push(pos[p-1]); } if(p<k) { if(!vis[p+1]) { vis[p+1]=1; pos[p+1].c=cnt+1; pos[p+1].x=p+1; q.push(pos[p+1]); } if(!vis[2*p]) { vis[2*p]=1; pos[2*p].c=cnt+1; pos[2*p].x=2*p; q.push(pos[2*p]); } } } } int main() { cin>>n>>k; memset(vis,0,sizeof(vis)); memset(pos,0,sizeof(pos)); vis[n]=1; pos[n].x=n; pos[n].c=0; q.push(pos[n]); cout<<bfs()<<endl; return 0; }

最后

以上就是含糊棒球最近收集整理的关于抓牛(poj4001)BFS的全部内容,更多相关抓牛(poj4001)BFS内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(62)

评论列表共有 0 条评论

立即
投稿
返回
顶部