農夫知道一頭牛的位置，想要抓住它。農夫和牛都位于數軸上，農夫起始位于點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;}這題沒啥要描述的。理解后再做迷宮最短路徑就容易很多了..
新聞熱點
疑難解答
