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
Output
Sample Input
5 17
Sample Output
4
Hint
Source
抽象的广度优先搜索。
队列q定义为全局变量时ac，但是放到bfs函数里面就会wa，可能队列中元素太多导致栈溢出，而全局变量不容易溢出。
#include <iostream> #include <queue> #include <cstdio> using namespace std; const int size = 100001; bool mark[size]; int dist[size]; queue<int> q; int bfs(int N, int K) { q.push(N); dist[N] = 0; mark[N] = true; int i, v, w; while (!q.empty()) { v = q.front(); q.pop(); for (i = 0; i < 3; i++) { if (i == 0) w = v - 1; else if (i == 1) w = v + 1; else w = v * 2; if (w < 0 || w >= size) continue; if (!mark[w]) { mark[w] = true; q.push(w); dist[w] = dist[v] + 1; } if (w == K) return dist[w]; } } } int main() { int N, K; scanf("%d%d", &N, &K); if (N >= K) printf("%d\n", N - K); else printf("%d\n", bfs(N, K)); return 0; }
原文：https://www.cnblogs.com/lxc1910/p/10466728.html