文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
最基础的广搜题，拿<queue>玩一下...
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: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Output
For each k given in the input, print one line containing ak to the output.
Sample Input
5 17
Sample Output
4
Slyar:USACO的题，给出2个数n和k，问从n经过+1或者-1或者*2能到达k的最小步数。分3个方向BFS，找到后树的深度就是最小步数了。注意n可以比k大，这时只有-1一种办法可以从n到达k，直接减就行了，还有要注意边界的判断...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> #include <queue> #define SIZE 100001 using namespace std; queue<int> x; bool visited[SIZE]; int step[SIZE]; int bfs(int n, int k) { int head, next; //起始节点入队 x.push(n); //标记n已访问 visited[n] = true; //起始步数为0 step[n] = 0; //队列非空时 while (!x.empty()) { //取出队头 head = x.front(); //弹出队头 x.pop(); //3个方向搜索 for (int i = 0; i < 3; i++) { if (i == 0) next = head - 1; else if (i == 1) next = head + 1; else next = head * 2; //越界就不考虑了 if (next > SIZE || next < 0) continue; //判重 if (!visited[next]) { //节点入队 x.push(next); //步数+1 step[next] = step[head] + 1; //标记节点已访问 visited[next] = true; } //找到退出 if (next == k) return step[next]; } } } int main() { int n, k; cin >> n >> k; if (n >= k) { cout << n - k << endl; } else { cout << bfs(n, k) << endl; } return 0; } |
