游客 注册 | 登录
中文 | En

2635 - 白云校区的奶牛

通过次数

0

提交次数

0

时间限制 : 2 秒 内存限制 : 128 MB

白云校区的食品学院最近养了只奶牛作奶品分析，最近下大雨奶牛趁机走丢了，小明被告知奶牛正在某位置上吃草，他很想尽快捉住它。假设小明刚开始在位置X (0 ≤X≤ 100,000)，假设他与奶牛在一条直线上，奶牛在位置Y (0 ≤Y≤ 100,000)。小明有两种移动的方法：走路或瞬间移动：

(1)走路，小明可以在1秒钟从位置X 走到位置X – 1和位置X + 1;

(2)瞬间转移，小明可以在1秒钟从位置X 转移到位置2X。

由于奶牛不知道小明在追它，它在整个过程一动不动在吃草，问小明最短多长时间可以捉到这只奶牛。


题目输入

有多行数据，每一行有两个整数X, Y


题目输出

每一行输出小明捉住奶牛最短时间（秒）


输入/输出样例

输入格式

5 17
1 2

输出格式

4
1

C语言解答

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int n,m,t1,t2,a[400010],b[400010],c[400010],pp,i;
int main()
{
        while(scanf("%d%d",&n,&m)!=EOF)
        {
                if(n==m)
                {
                        printf("0\n");
                        continue;
                }
                for(i=0;i<=200000;i++)
                a[i]=0;
        t1=0;t2=1;b[1]=n;
        c[1]=0;a[n]=1;
        while(1)
        {
                t1++;
                if(t1>t2)break;
                if((a[b[t1]-1]==0)&&(b[t1]-1>=0))
                {
                        t2++;
                        a[b[t1]-1]=1;
                        b[t2]=b[t1]-1;
                        c[t2]=c[t1]+1;
                        if(b[t2]==m)
                        {
                                pp=c[t2];
                                break;
                        }
                }
                if((a[b[t1]+1]==0)&&(b[t1]+1<=2*m))
                {
                        t2++;
                        a[b[t1]+1]=1;
                        b[t2]=b[t1]+1;
                        c[t2]=c[t1]+1;
                        if(b[t2]==m)
                        {
                                pp=c[t2];
                                break;
                        }
                }
                if((a[b[t1]*2]==0)&&(b[t1]*2<=2*m))
                {
                        t2++;
                        a[b[t1]*2]=1;
                        b[t2]=b[t1]*2;
                        c[t2]=c[t1]+1;
                        if(b[t2]==m)
                        {
                                pp=c[t2];
                                break;
                        }
                }
        }
        printf("%d\n",pp);
        }
}

C++解答

//改自http://poj.org/problem?id=3278
#include<iostream>
#include <queue>
#include <string.h> //for memset
using namespace std;
int dir[3][2]={{1,1},{1,-1},{2,0}};
const int NN = 100001;
int vis[NN], step[NN];


int bfs(int N, int K)
{
    int dir[3][2] = {{1, 1}, {1, -1}, {2, 0}};
    int next, i, current;
    queue<int> qs;
    
    qs.push(N);
    vis[N] = 1;
    step[N] = 0;
    while (!qs.empty())    
    {
        current = qs.front();
        qs.pop();
        
        if (current == K)
            return step[current];
        
        for (i = 0; i < 3; i++)  
        {
            next = dir[i][0] * current + dir[i][1];
            
            if (next >= NN || next <0)
                continue;
            
            if (vis[next] != 0)
                continue;
            
            vis[next] = 1;
            step[next] = step[current] + 1;
            qs.push(next);
        }
    }
    return -1;
}


int main()
{
    int N, K;
    while(cin>>N>>K)
    {
        memset(vis, 0, sizeof(vis));
        
        cout<<bfs(N, K)<<endl;
    }
    return 0;
}

Java解答

import java.util.*;
public class Main {
	static int[] num=null;
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int x,y,i,j;
		while(in.hasNext()){
			 num =new int[100001];
			x = in.nextInt();
			y = in.nextInt();
			System.out.println(Method(x,y));
			
		}
	}
	public static int Method(int x,int y){
		ArrayList<Integer> ai = new ArrayList<Integer>();
		num[x]=1;
		int count=1;
		int tem=0;
		if(x==y) return 0;
		//把x加入队列，
		ai.add(x);	
		while(ai.size()!=0){
			tem=ai.get(0);
			ai.remove(0);
			if(tem==y) {return num[tem]-1; }
			if(num[tem]==count)
			count++;
			
			if(2*tem<=100000&&num[2*tem]==0){
				ai.add(2*tem);
				num[2*tem]=count;
			}
			if(tem+1<=100000&&num[tem+1]==0){
				ai.add(tem+1);
				num[tem+1]=count;
			}
			if(tem-1>=0&&num[tem-1]==0){
				ai.add(tem-1);
				num[tem-1]=count;
			}
			
		}
		return count-1;
		
	}
	
}
请先登陆