- POJ 3278 - Catch That Cow
- Time: 2000MS
- Memory: 65536K
- 难度: 初级
- 分类: BFS
0x00 POJ 原题
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
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.
Source
0x10 题目概述
给定两个整数 n 和 k
通过 n+1 或 n-1 或 n*2 这 3 种操作,使得 n==k
输出最少的操作次数
0x20 解题思路
水题,三入口的 BFS。
注意的地方有二:
- 由于用于广搜的 队列数组 和 标记数组 相当大,如果定义这两个数组时把它们扔到局部去,编译是可以的,但肯定执行不了,提交就等 RE 吧。 大数组必须开为 全局,这是常识。。
- 剪枝:直接广搜一样等着 RE 吧 (不剪枝的同学输入
n=0k=100000试试)。。。具体怎么剪枝看程序
0x30 AC 源码
//Memory Time
//1292K 0MS
#include<iostream>
using namespace std;
const int large=200030;
typedef class
{
public:
int x;
int step;
}pos;
int n,k;
bool vist[large]; //数组较大,必须开为全局数组,不然肯定RE
pos queue[large];
void BFS(void)
{
int head,tail;
queue[head=tail=0].x=n;
queue[tail++].step=0;
vist[n]=true;
while(head<tail)
{
pos w=queue[head++];
if(w.x==k)
{
cout<<w.step<<endl;
break;
}
if(w.x-1>=0 && !vist[w.x-1]) //w.x-1>=0 是剪枝
{
vist[w.x-1]=true;
queue[tail].x=w.x-1;
queue[tail++].step=w.step+1;
}
if(w.x<=k && !vist[w.x+1]) //w.x<=k 是剪枝
{
vist[w.x+1]=true;
queue[tail].x=w.x+1;
queue[tail++].step=w.step+1;
}
if(w.x<=k && !vist[2*w.x]) //w.x<=k 是剪枝
{
vist[2*w.x]=true;
queue[tail].x=2*w.x;
queue[tail++].step=w.step+1;
}
}
return;
}
int main(void)
{
while(cin>>n>>k)
{
memset(vist,false,sizeof(vist));
BFS();
}
return 0;
}