[kuangbin带你飞]专题一 简单搜索 POJ-3278

题目描述

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

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.

解题思路

本题大意就是在一维的一条路上，有一个农夫，和一头奶牛，农夫要捉奶牛，奶牛是保持不动的，农夫可以以三种方式移动：X+1、X-1、X2。每次移动消耗一分钟，输入农夫和奶牛的位置，输出农夫捉到奶牛所用的最短时间。 遇到求最短时间的问题一般使用BFS即可，这道题是一维的BFS，移动方式有三种：X+1、X-1、X2。下面给出AC代码

代码

#include<cstdio> #include<iostream> #include<queue> #include <vector> #include <algorithm> #include<string.h> #define MAX_SIZE 100000 using namespace std; struct node { int L,step; }; int N,K; vector<int> v; int mark[100001]; bool isvalid(int L) { sort(v.begin(), v.end()); if(binary_search(v.begin(), v.end(), L)) return false; return true; } int bfs(int S) { if(S==K) return 0; node new_node,next_node; int L; next_node.L = S; next_node.step = 0; queue<node> que; // v.push_back(S); mark[S] = 1; que.push(next_node); while(!que.empty()) { new_node = que.front(); que.pop(); L = new_node.L; if(L+1==K||L-1==K||L*2==K) return new_node.step+1; if(L-1>=0&&mark[L-1]==0) { next_node.L = L-1; next_node.step = new_node.step+1; que.push(next_node); mark[L-1] = 1; // cout<<next_node.L<<" "; // v.push_back(L-1); } if(L+1<=100000&&mark[L+1]==0) { next_node.L = L+1; next_node.step = new_node.step+1; que.push(next_node); // v.push_back(L+1); mark[L+1] = 1; // cout<<next_node.L<<" "; } if(L*2<=100000&&mark[L*2]==0) { next_node.L = L*2; next_node.step = new_node.step+1; que.push(next_node); mark[L*2] = 1; // cout<<endl; // cout<<next_node.L<<" "; // v.push_back(L*2); } } // return -1; } int main() { int minutes; // while(scanf("%d%d",&N,&K)==2) // cin>>N>>K; // memset(mark,0,sizeof(mark)); // minutes = bfs(N); cout<<endl; // printf("%d\n",minutes); while(cin>>N>>K) { memset(mark,0,sizeof(mark)); minutes = bfs(N); // cout<<endl; printf("%d\n",minutes); // v.clear(); } return 0; }

遇到的坑

本题思路很简单，但是我的代码一开始一直WA，样例是可以正常输出的，一些边缘数据没有覆盖到。经过检查，发现，当农夫和奶牛在相同位置时候，应该是输出0，但是我的代码写的时候没考虑这个情况，因此一直WA