POJ3278，Catch That Cow

POJ3278，Catch That Cow

Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 46459 Accepted: 14574

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 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 orX + 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 andK

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的位置，牛不動，若農夫任意時間在X，農夫可走到X+1，X-1,2*X三個位置，問農夫幾次可抓到牛

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

public class POJ3278_ieayoio {
	public static boolean[] f;

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			int n = cin.nextInt();
			int k = cin.nextInt();
			System.out.println(bfs(n, k));
		}
	}

	static int bfs(int n, int k) {
		// Queue queue = new LinkedList();
		Queue queue = new ArrayDeque();
		f = new boolean[100010];
		Arrays.fill(f, true);//標記是否曾走過
		Node node = new Node(n, 0);
		f[n] = false;
		queue.offer(node);//初始值直接入隊
		while (!queue.isEmpty()) {
			node = queue.poll();//出隊
			if (node.location == k) {
				return node.step;
			}
			Node el;
			if (node.location < k && f[node.location + 1]) {
				el = new Node(node.location + 1, node.step + 1);
				f[node.location + 1] = false;
				queue.offer(el);
			}
			if (node.location - 1 >= 0 && f[node.location - 1]) {
				el = new Node(node.location - 1, node.step + 1);
				f[node.location - 1] = false;
				queue.offer(el);
			}
			//當node.location大於k是只能選擇後退
			//node.location * 2 <= 100000是坐標軸的范圍，開始沒加就Runtime Error了
			if (node.location < k && node.location * 2 <= 100000
					&& f[node.location * 2]) {
				el = new Node(node.location * 2, node.step + 1);
				f[node.location * 2] = false;
				queue.offer(el);
			}
		}

		return node.step;
	}
}

class Node {
	int location;//位置
	int step;//步數

	Node(int location, int step) {
		this.location = location;
		this.step = step;
	}
}

標記是否曾經走過是這道題解決超時的辦法