描述

農夫知道一頭牛的位置，想要抓住它。農夫和牛都位于數軸上，農夫起始位于點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<cstring> #include<cstdio> #define MAX 100000 using namespace std; struct hp{int num,step; }queue[100005]; int n,m,head,tail,now,step,ans; bool b[100005]; int main(){scanf("%d%d",&n,&m);ans=MAX;head=0,tail=1;queue[tail].num=n,queue[tail].step=0,b[n]=true;while (head<tail){++head;now=queue[head].num,step=queue[head].step;if (now==m) {printf("%d",step);return 0;}if (now+1<=MAX&&!b[now+1]) b[now+1]=true,queue[++tail].num=now+1,queue[tail].step=step+1;if (now-1>=0&&!b[now-1]) b[now-1]=true,queue[++tail].num=now-1,queue[tail].step=step+1;if (now*2<=MAX&&!b[now*2]) b[now*2]=true,queue[++tail].num=now*2,queue[tail].step=step+1; } }

總結

以上是生活随笔為你收集整理的【openjudge】抓住那头牛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。