POJ 3278 Catch That Cow(BFS,闆子題)Catch That Cow

Time Limit: 2000MS

Memory Limit: 65536K

Total Submissions: 88732

Accepted: 27795

Description

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?

Input

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

Output

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

Sample Input

Sample Output

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

<a href="http://poj.org/searchproblem?field=source&amp;key=USACO+2007+Open+Silver">USACO 2007 Open Silver</a>

題目連結：http://poj.org/problem?id=3278

題意：有一個農民和一頭牛，他們在一個數軸上，牛在k位置保持不動，農戶開始時在n位置。設農戶目前在M位置，每次移動時有三種選擇：1.移動到M-1；2.移動到M+1位置；3.移動到M*2的位置。問最少移動多少次可以移動到牛所在的位置。是以可以用廣搜來搜尋這三個狀态，直到搜尋到牛所在的位置。

分析：BFS的闆子題，用隊列做，第一次學隊列，感覺自己好弱啊！現在才學，算法真的好難學，學了又怕不會用，現在不敢學太快了！

下面每一步代碼我都給出了詳細解釋，一看就懂！