农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：
1、从X移动到X-1或X+1，每次移动花费一分钟2、从X移动到2*X，每次移动花费一分钟假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？输入两个整数，N和K输出一个整数，农夫抓到牛所要花费的最小分钟数样例输入5 17样例输出4这题用深搜肯定会炸，超时。数据太大了。
广搜
#include<iostream>#include <queue>#include<cstdio>using namespace std;int main(){ int n, k; cin >> n >> k; queue<int> que; int map[100001]; for (int i = 0; i < 100001; i++) map[i] = 100000; map[n] = 0; que.push(n); while (que.size()){ int num = que.front(); que.pop(); if (num == k) break; if (num + 1 <= 100000 && map[num + 1] == 100000) { map[num + 1] = map[num] + 1; que.push(num + 1); } if (num - 1 >= 0 && map[num - 1] == 100000){ map[num - 1] = map[num] + 1; que.push(num - 1); } if (2 * num <= 100000 && map[2 * num] == 100000){ map[2 * num] = map[num] + 1; que.push(2 * num); } } cout << map[k] << endl; return 0;}这题没啥要描述的。理解后再做迷宫最短路径就容易很多了..
新闻热点
疑难解答
