描述

農(nóng)夫知道一頭牛的位置，想要抓住它。農(nóng)夫和牛都位于數(shù)軸上，農(nóng)夫起始位于點(diǎn)N(0<=N<=100000)，牛位于點(diǎn)K(0<=K<=100000)。農(nóng)夫有兩種移動方式：

1、從X移動到X-1或X+1，每次移動花費(fèi)一分鐘 2、從X移動到2*X，每次移動花費(fèi)一分鐘
假設(shè)牛沒有意識到農(nóng)夫的行動，站在原地不動。農(nóng)夫最少要花多少時間才能抓住牛？

輸入

兩個整數(shù)，N和K

輸出

一個整數(shù)，農(nóng)夫抓到牛所要花費(fèi)的最小分鐘數(shù)

樣例輸入

5 17

樣例輸出

4

這題用深搜肯定會炸，超時。數(shù)據(jù)太大了。

廣搜

#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; }這題沒啥要描述的。理解后再做迷宮最短路徑就容易很多了..

總結(jié)

以上是生活随笔為你收集整理的抓住那头牛（广搜）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。