描述

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

1、從X移動(dòng)到X-1或X+1，每次移動(dòng)花費(fèi)一分鐘

2、從X移動(dòng)到2*X，每次移動(dòng)花費(fèi)一分鐘

假設(shè)牛沒有意識(shí)到農(nóng)夫的行動(dòng)，站在原地不動(dòng)。農(nóng)夫最少要花多少時(shí)間才能抓住牛？

格式

輸入格式

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

輸出格式

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

樣例

輸入樣例

5 17

輸出樣例

4

限制

時(shí)間限制: 1000 ms

內(nèi)存限制: 65536 KB

廣搜，例如樹的層次排序，一層一層的去搜。深搜，一條路走到底

#include <iostream> #include <queue> #include <string.h> using namespace std;void bfs(int n, int k) {int step[3]; //每次都有三種選擇去走 int visit[100005]; //用來(lái)記最小時(shí)間queue<int> q; //隊(duì)列memset(step, 0, sizeof(step));memset(visit, -1, sizeof(visit));q.push(n); //入隊(duì)visit[n] = 0; //起點(diǎn)為0分鐘while (!q.empty()) {int cur = q.front(); //取隊(duì)頭數(shù)據(jù)q.pop(); //刪隊(duì)頭數(shù)據(jù)if (cur == k) { //當(dāng)抓住牛時(shí)break;}step[0] = cur * 2; step[1] = cur + 1;step[2] = cur - 1;for (int i=0; i<3; i++) { //廣搜入隊(duì)if (step[i] >= 0 && step[i] < 100001 && visit[step[i]] == -1) {q.push(step[i]);visit[step[i]] = visit[cur] + 1; //記錄時(shí)間}}}printf ("%d\n", visit[k]); }int main() {int n, k;scanf ("%d %d", &n, &k);bfs(n, k);return 0; }

?

總結(jié)

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

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