首页 > > 程序设计 > C/C++ >

POJ 3278 Catch That Cow（BFS）

2018-06-17 22:15:06来源：未知阅读 ()

题目网址：http://poj.org/problem?id=3278

题目：

Catch That Cow

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 92360		Accepted: 28999

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.

思路：

很简单的一道BFS题。总共只有三种操作，每次都取队首元素分别进行三种操作，再对操作结果进行判断，筛去负数和超过100,000（边界值）的情况，其他情况都入队。

代码：

 1 #include <cstdio>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 int visited[100005];
 6 int n,k;
 7 queue<int>q;
 8 void bfs(){
 9     q.push(n);
10     while (!q.empty()) {
11         int x=q.front();q.pop();
12         if(x==k){
13             printf("%d\n",visited[x]-1);//初始次数为1，结果减去1
14             return ;
15         }
16         if(x-1>=0 && !visited[x-1]){//负数不考虑
17             q.push(x-1);
18             visited[x-1]=visited[x]+1;
19         }
20         if(x+1<=100000 && !visited[x+1]){//超过边界值的要筛去，否则会占用不必要的搜索时间
21             q.push(x+1);
22             visited[x+1]=visited[x]+1;
23         }
24         if(x*2<=100000 && !visited[x*2]){
25             q.push(x*2);
26             visited[x*2]=visited[x]+1;
27         }
28     }
29 }
30 int main(){
31     scanf("%d%d",&n,&k);
32     visited[n]=1;//初始位置也要赋值，防止第二次搜索到
33     bfs();
34     return 0;
35 }