Think: BFS +隊列 題目， 農夫有兩種種不同的移動方式
PRoblem 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. Example Input
5 17
Example Output
4
題目大意： 1. 數軸上有Ａ Ｂ２點 2. 農夫 有兩種移動方式：walk 每分鐘移動一格 Teleporting 每次移動 ２＊i個單位 ３．求最短時間
#include<bits/stdc++.h> using namespace std; bool v[1000005]; int step[1000005]; void BFS(int n, int k); queue<int>q; int main() { int n, k; while(cin >> n >> k) { while(!q.empty()) q.pop(); memset(v, 0, sizeof(v)); if (n >= k) cout << n - k << endl; else BFS(n, k); } return 0; } void BFS(int n, int k) { int head, next, i; q.push(n); step[n] = 0; while(!q.empty()) { head = q.front(); q.pop(); for (i = 0;i < 3;i ++) { if (i == 0) next = head + 1; if (i == 1) next = head - 1; if (i == 2) next = head * 2; if (next < 0 || next > 100000) continue ; if (v[next] == 0) { q.push(next); step[next] = step[head] + 1; v[next] = 1; } if (next == k) { cout << step[next] << endl; return ; } } } }/***************************************************User name: Result: AcceptedTake time: 0msTake Memory: 468KBSubmit time: 2017-02-18 19:26:43****************************************************/新聞熱點
疑難解答
