首页 > 代码库 > POJ3278，Catch That Cow

POJ3278，Catch That Cow

2024-07-16 13:33:39   226人阅读

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<Node> queue = new LinkedList<Node>();
		Queue<Node> queue = new ArrayDeque<Node>();
		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;
	}
}



标记是否曾经走过是这道题解决超时的办法


联系
我们