题意：农夫的牛跑了，给出农夫和牛在坐标轴上的位置n和k，农夫每次只能从点n移动到n-1、n+1或者n*2的位置。输出抓到牛所需要的最小移动次数。
思路：思路明显的bfs，每次搜索只按照这三种方式，标记访问过的点防止重复访问即可。
#include<bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f typedef long long LL; typedef pair<int,int> P; const int N=1000000+5; int g[N],n,k; int bfs(){ if(n==k)return 0; queue<int> q; q.push(n); while(q.size()){ int p=q.front(); q.pop(); if(p-1>=0&&p-1<=1000000&&g[p-1]==-1){ g[p-1]=g[p]+1; if(p-1==k)return g[p-1]; q.push(p-1); } if(p+1>=0&&p+1<=1000000&&g[p+1]==-1){ g[p+1]=g[p]+1; if(p+1==k)return g[p+1]; q.push(p+1); } if(p*2>=0&&p*2<=1000000&&g[p*2]==-1){ g[p*2]=g[p]+1; if(p*2==k)return g[p*2]; q.push(p*2); } } } int main(){ while(~scanf("%d%d",&n,&k)){ memset(g,-1,sizeof(g)); g[n]=0; printf("%d\n",bfs()); } }
