Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 89585 Accepted: 28099 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 minuteTeleporting: 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 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. 题意：从n到k，有三种移动方法，-1，+1，*2； dfs三种走法， 注意：1.减枝 2.vis标记是否走过，step记录步数
#include<stdio.h> #include<queue> #include<string> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int n,k; int ans; int vis[100001],step[100001]; queue<int>c; int dfs(int n,int ans) { vis[n]=1; step[n]=0; c.push(n); //cout<<"123"<<endl; while(!c.empty()) { //cout<<"123"<<endl; int fist=c.front(); c.pop(); //printf("%d\n",fist); if(fist==k) return step[fist]; for(int i=0;i<3;i++) { int next=0; if(i==0) next=fist-1; else if(i==1) next=fist+1; else if(i==2) next=fist*2; if(next<0||next>=100001) continue; else { if(vis[next]==0) { vis[next]=1; step[next]=step[fist]+1; c.push(next); } } } } } int main() { memset(vis,0,sizeof(vis)); memset(step,0,sizeof(step)); while(!c.empty()) c.pop(); scanf("%d%d",&n,&k); int aa=dfs(n,0); printf("%d\n",aa); return 0; }