poj3278

Catch That Cow

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 71899		Accepted: 22632

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.

Source

USACO 2007 Open Silver

大致题意：

给定两个整数n和k

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

输出最少的操作次数

bfs思想：节点进行广度优先搜索的顺序。

搜索实现方法（非递归）：

算法思想：1.设置一个队列Q，从顶点出发，遍历该顶点后让其进队；

2.出队一个顶点元素，求该顶点的所有邻接点（对应于此题即FJ的三种走法），

对于没有遍历过的邻接点遍历之，并让其进队；

3.若队空停止，队不空时继续第2步。

代码一：C++STL&&bfs版本：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define N 100010
int step[N],vis[N];
queue<int>q;
int bfs(int n,int k){
    int now,next;
    step[n]=0;
    vis[n]=1;
    q.push(n);
    while(!q.empty()){
        now=q.front();
        q.pop();
        for(int i=0;i<3;i++){
            if(i==0) next=now-1;
            else if(i==1) next=now+1;
            else if(i==2) next=now*2;
            if(next<0||next>N) continue;
            if(!vis[next]){
                vis[next]=1;
                q.push(next);
                step[next]=step[now]+1; 
            }
            if(next==k) return step[next];
        }
    }
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    if(n>=k) printf("%d
",n-k);  
    else printf("%d
",bfs(n,k));
    return 0;
}

代码二：C语言+bfs+模拟队列版本

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
struct node{
    int x,step;
}q[N];
int vis[N];
int bfs(int n,int k){
    node now,next;
    int head=0,tail=1;
    q[head].x=n;
    q[head].step=0;
    vis[n]=1;
    while(head<tail){
        now=q[head++];
        for(int i=0;i<3;i++){
            if(i==0) next.x=now.x-1;
            else if(i==1) next.x=now.x+1;
            else if(i==2) next.x=now.x*2;
            if(next.x<0||next.x>N) continue;
            if(!vis[next.x]){
                vis[next.x]=1;
                next.step=now.step+1;
                q[tail++]=next;
            }
            if(next.x==k) return next.step;
        }

    }
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    if(n>=k) printf("%d
",n-k);  
    else printf("%d
",bfs(n,k));
    return 0;
}

3.换种风格

#include<iostream>
#include<queue>
using namespace std;
int a[100001],b[100001];
int main()
{
    int m,n,y;
    queue<int>que;
    cin>>m>>n;
    que.push(m);
    a[m]=0;
    while(!que.empty()){
        y=que.front();que.pop();
        b[y]=1;
        if(y==n) break;
        if(y-1>=0&&b[y-1]==0){
            que.push(y-1);
            a[y-1]=a[y]+1;
            b[y-1]=1;
        }
        if(y+1<=100000&&b[y+1]==0){
            que.push(y+1);
            a[y+1]=a[y]+1;
            b[y+1]=1;
        }
        if(2*y<=100000&&b[2*y]==0){
            que.push(2*y);
            a[2*y]=a[y]+1;
            b[2*y]=1;
        }
    }
    cout<<a[y]<<endl;
    return 0;
}

注：hdu同题

http://acm.hdu.edu.cn/showproblem.php?pid=2717

是输入若干组数据