BZOJ 1646: [Usaco2007 Open]Catch That Cow 抓住那只牛 (BFS)
1646: [Usaco2007 Open]Catch That Cow 抓住那只牛
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 915 Solved: 441 [Submit][Status][Discuss]
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?
农夫约翰被通知，他的一只奶牛逃逸了！所以他决定，马上幽发，尽快把那只奶牛抓回来．
他们都站在数轴上．约翰在N(O≤N≤100000)处，奶牛在K(O≤K≤100000)处．约翰有
两种办法移动，步行和瞬移：步行每秒种可以让约翰从z处走到x+l或x-l处；而瞬移则可让他在1秒内从x处消失，在2x处出现．然而那只逃逸的奶牛，悲剧地没有发现自己的处境多么糟糕，正站在那儿一动不动．
那么，约翰需要多少时间抓住那只牛呢？
Input
- Line 1: Two space-separated integers: N and K
仅有两个整数N和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 Farmer John starts at point 5 and the fugitive cow is at point 17.
Sample Output
4
OUTPUT DETAILS:
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes.
大概是写得第一道bfs了。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年04月10日 星期日 21时00分01秒
4File Name :code/bzoj/1646.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n,k;
35bool vis[N];
36int d[N];
37void bfs()
38{
39 ms(d,-1);
40 queue<int>q;
41 q.push(n);
42 vis[n] = true;
43 d[n] = 0 ;
44
45 while (!q.empty())
46 {
47 int px = q.front () ; q.pop();
48 if (px==k)
49 {
50 return ;
51 }
52 int nxt[3];
53 nxt[0] = px-1;
54 nxt[1] = px+1;
55 nxt[2] = 2*px;
56 for ( int i = 0 ; i < 3 ; i++)
57 {
58 if (nxt[i]>=0&&nxt[i]<=100000&&!vis[nxt[i]])
59 {
60 q.push(nxt[i]);
61 vis[nxt[i]] = true;
62 d[nxt[i]] = d[px] + 1;
63 }
64 }
65 }
66}
67int main()
68{
69 #ifndef ONLINE_JUDGE
70 freopen("code/in.txt","r",stdin);
71 #endif
72
73 scanf("%d %d",&n,&k);
74 bfs();
75 printf("%d\n",d[k]);
76
77 #ifndef ONLINE_JUDGE
78 fclose(stdin);
79 #endif
80 return 0;
81}