30天学会基础算法 (抓住那头牛—BFS) ^1^
题目描述
农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤10000)，牛位于点K(0≤K≤10000)。农夫有两种移动方式：
1.从X移动到X-1或X+1，每次移动花费一分钟
2.从X移动到2*X，每次移动花费一分钟
假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？
输入
两个整数，N和K。
输出
一个整数，农夫抓到牛所要花费的最小分钟数。
样例输入
5 17
样例输出
4
样例分析
每次对当前位置-1，+1，*2获取下一分钟能够到达的位置
- 题解
#include#includeusing namespace std;const int N = 1e5 + 10;//数据范围，根据题意而定int a[N], s[N];//a数组表示所能到达的位置，，用s数组更新aint n, k;//农夫的位置与牛的位置void bfs(int x){for (int i = 1; i <= pow(3, x); i++) {if (a[i] == k)//找到了牛{cout << x;return;}s[i] = a[i];//用s保存当前a的值}//三种选择，-1，+1，*2，每三个为一组for (int i = 1; i <= pow(3, x); i++){a[3 * i - 2] = s[i] + 1;a[3 * i - 1] = s[i] - 1;a[3 * i] = s[i] * 2;}bfs(x + 1);//搜索下一分钟}int main() {cin >> n >> k;a[1] = n;//起点为nbfs(0);return 0;}- 无注释版
#include#includeusing namespace std;const int N = 1e7 + 10;int a[N], s[N];int n, k;void bfs(int x){for (int i = 1; i <= pow(3, x); i++) {if (a[i] == k){cout << x;return;}s[i] = a[i];}for (int i = 1; i <= pow(3, x); i++){a[3 * i - 2] = s[i] + 1;a[3 * i - 1] = s[i] - 1;a[3 * i] = s[i] * 2;}bfs(x + 1);}int main() {cin >> n >> k;a[1] = n;bfs(0);return 0;}
