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.





题意：在一维的直线上，给出John的位置n，和cow的位置k，求出John按照给定三种规则找到cow的最少步数。

分析：用广度优先搜索从源点开始，依次用三种规则进行查找，设置边界条件，最先找到的即为最优解。这里还要注意下数组边界大小要比用于比较的边界要大一点，否则会数组越界而RE，我在这里吃了6个RE，一直没找到原因。后来才惊奇地发现时用于比较的MAX和数组大小Max相同。

import java.util.LinkedList;

import java.util.Scanner;

public class Main {

	static int start, end;

	static int MAX = 200000;

	static LinkedList<Integer> q;

	static boolean[] visited;

	static int[] step;

	static int t, next;

	static int bfs() {

		q.add(start);

		visited[start] = true;

		step[start] = 0;

		while (!q.isEmpty()) {

			t = q.poll();

			for (int i = 0; i < 3; i++) {

				if (i == 0) {

					next = t - 1;

				} else if (i == 1) {

					next = t + 1;

				} else {

					next = t * 2;

				}

				if (next > MAX || next < 0)

					continue;

				if (!visited[next]) {

					q.add(next);

					step[next] = step[t] + 1;

					visited[next] = true;

				}

				if (next == end)

					return step[next];

			}

		}

		return -1;

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		q = new LinkedList<Integer>();

		//在这个地方比MAX多加上5，放在RE

		visited = new boolean[MAX+5];

		step = new int[MAX+5];

		start = sc.nextInt();

		end = sc.nextInt();

		if (start >= end) {

			System.out.println(start - end);

		} else {

			System.out.println(bfs());

		}

	}

}

版权声明：本文为博主原创文章，未经博主允许不得转载。