首页 > 搜索 > BFS搜索 > POJ 3278 Catch That Cow [解题报告] Java
2013
11-12

POJ 3278 Catch That Cow [解题报告] Java

Catch That Cow

问题描述 :

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?

输入:

Line 1: Two space-separated integers: N and K

输出:

Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.

样例输入:

5 17

样例输出:

4

温馨提示:

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.

解题代码:

解法一:				
import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
  
public class Main {   
  
    public static final int MAX = 200000;   
  
    public static void main(String[] args) {   
  
        Scanner scan = new Scanner(new BufferedInputStream(System.in));   
        if (scan.hasNext()) {   
            int n = scan.nextInt();   
            int k = scan.nextInt();   
            System.out.println(catchTheCow(n, k));   
        }   
    }   
  
    public static int catchTheCow(int n, int k) {   
        if (n == k) {   
            return 0;   
        }   
        LinkedList queue = new LinkedList();   
        boolean[] visited = new boolean[MAX + 5];   
        int[] minutes = new int[MAX + 5];   
        visited[n] = true;   
        queue.add(n);   
        while (!queue.isEmpty()) {   
            int current = queue.removeFirst();   
            for (int i = 0; i < 3; i++) {   
                int next = current;   
                if (i == 0) {   
                    next++;   
                } else if (i == 1) {   
                    next--;   
                } else if (i == 2) {   
                    next <<= 1;   
                }   
                if (next < 0 || next > MAX) {   
                    continue;   
                }   
                if (!visited[next]) {   
                    queue.add(next);   
                    visited[next] = true;   
                    minutes[next] = minutes[current] + 1;   
                }   
                if (next == k) {   
                    return minutes[k];   
                }   
            }   
        }   
  
        return 0;   
    }   
}  

解法二:
import java.io.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
   InputStreamReader is=new InputStreamReader(System.in);
   BufferedReader in=new BufferedReader(is);
   String[] ss=in.readLine().split(" ");
   int a=Integer.parseInt(ss[0]);
   int b=Integer.parseInt(ss[1]);
   if(a>=b){
	System.out.println(a-b);
	System.exit(0);
   }
   int cnt=0;
   if(a==0){
	a++;
	cnt++;
    }
    while(a< b)
    {
	a*=2;
	cnt++;
    }
    if(a==b){
	System.out.println(cnt);
	System.exit(0);
    }
    a/=2;cnt--;
    int g=(int) Math.pow(2,cnt);
    int l=2*a-b;
    int n=g*2;
    int h=cnt+1+f(l,n);
    int u=b-a;
    int k=cnt+f(u,g);
    System.out.println(Math.min(k,h));
  }

public static int f(int l,int n)
  {
   if(n==0)return 0;
   int h=l%n;
   int a=f(n-h,n/2)+l/n+1;
   int b=f(h,n/2)+l/n;
   return Math.min(a, b);
  }
}

  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept