如何才能在POJ 3278 Catch That Cow中成功捕捉到那头牛？

本文共计784个文字，预计阅读时间需要4分钟。

Catch That Cow! 时间限制：2000MS 内存限制：65536K 总提交：44220 接受：13814

描述：农场主约翰得知了一头逃亡牛的位置，他想要立即抓住它。他从一个点N开始（0 ≤ N ≤ 100000），目标是尽快捕获这头牛。

输入：第一行包含一个整数N，表示农场主约翰的起始位置。第二行包含一个整数M，表示牛的位置数量。接下来M行，每行包含一个整数，表示牛的位置。

输出：输出一个整数，表示农场主约翰捕获牛所需的最短时间（以毫秒为单位）。

示例输入：

53

13

4

示例输出：

2

Catch That Cow

Time Limit:2000MS

Memory Limit:65536K

Total Submissions:44220

Accepted:13814

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a pointN(0 ≤N≤ 100,000) on a number line and the cow is at a pointK(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 pointXto the pointsX- 1 orX+ 1 in a single minute
* Teleporting: FJ can move from any pointXto the point 2 ×Xin 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: Nand 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

USACO 2007 Open Silver

大致题意：

给定两个整数n和k

通过n+1或n-1或n*2这3种操作，使得n==k

输出最少的操作次数

#include <stdio.h> #include <string.h> #include <stdlib.h> struct node { int x,ans; }q[1000005]; int jx[]={-1,1}; int n,k; int v[1000005]; void BFS() { struct node t,f; int i; int e=0,s=0; t.x=n; v[t.x]=1; t.ans=0; q[e++]=t; while(s<e) { t=q[s++]; if(t.x==k) { printf("%d\n",t.ans); break; } for(i=0;i<3;i++) { if(i==2) f.x=t.x*2; else f.x=t.x+jx[i]; if(v[f.x]==0&&f.x>=0&&f.x<=100000) { f.ans=t.ans+1; q[e++]=f; v[f.x]=1; } } } } int main() { while(scanf("%d%d",&n,&k)!=EOF) { memset(v,0,sizeof(v)); BFS(); } return 0; }