POJ-3278 Catch That Cow(BFS)

Catch That Cow

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 169075		Accepted: 51762

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

Hint

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.

Source

USACO 2007 Open Silver

首先拿道这个题以为是数论，用二进制捣鼓了半天依然没有什么发现

想到搜索，DFS or BFS？

DFS一般要整个遍历一遍再求解

BFS更适合解决一些最值问题，在最坏情况下和DFS的复杂度一致，但是一般情况下最值按照BFS都更易求

所以遇到一些最值搜索问题时可以考虑用BFS

变形的最短路应该看出来

无论BFS还是DFS都一定要注意标记已经走过的点！！！！！

这题在一些细节上还有待注意，比如说起止点可以是0，还有可以先乘到终止点后面再减回来

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <queue>
 5 #include <stack>
 6 #include <vector>
 7 #include <iostream>
 8 #include "algorithm"
 9 using namespace std;
10 const int MAX=100005;
11 int n,m,ans;
12 bool co[MAX];
13 struct num{
14     int x,y;
15 };
16 queue <num> q;
17 int main(){
18     freopen ("cow.in","r",stdin);
19     freopen ("cow.out","w",stdout);
20     int i,j;
21     scanf("%d%d",&n,&m);
22     memset(co,true,sizeof(co));
23     num a,b;a.x=n,a.y=0;
24     q.push(a);
25     co[a.x]=false;
26     while (!q.empty()){
27         a=q.front();q.pop();
28         if (a.x*2<MAX && co[a.x*2]){
29             b.x=a.x*2,b.y=a.y+1;
30             q.push(b);
31             co[b.x]=false;
32             if (b.x==m){ans=b.y;break;}
33         }
34         if (a.x+1<MAX && co[a.x+1]){
35             b.x=a.x+1,b.y=a.y+1;
36             q.push(b);
37             co[b.x]=false;
38             if (b.x==m){ans=b.y;break;}
39         }
40         if (a.x-1>=0 && co[a.x-1]){
41             b.x=a.x-1,b.y=a.y+1;
42             q.push(b);
43             co[b.x]=false;
44             if (b.x==m){ans=b.y;break;}
45         }
46     }
47     printf("%d",ans);
48     return 0;
49 }