题解 | #Catch That Cow#(BFS)
Description
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
- Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute
- Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: and
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
#include<iostream> #include<cstring> #include<queue> using namespace std; const int maxn=100001; struct status{//状态 int n; int t; status(int x,int y):n(x),t(y){} }; bool visit[maxn];//访问标记 int bfs(int n,int k){ queue<status>myque; myque.push(status(n,0));//初始状态入队 visit[n]=true; while(!myque.empty()){//广度优先搜索 status cur=myque.front();//取队头 myque.pop(); if(cur.n==k)return cur.t;//访问队头 for(int i=0;i<3;i++){//状态转移 status next(cur.n,cur.t+1);//时间++ if(i==0)next.n+=1; else if(i==1)next.n-=1; else if(i=2)next.n*=2; if(next.n<0||next.n>maxn||visit[next.n])continue;//越界或者已被访问 myque.push(next); visit[next.n]=true; } } } int main(){ int n,k; while(scanf("%d%d",&n,&k)!=EOF){ memset(visit,false,sizeof(visit)); printf("%d\n",bfs(n,k)); } return 0; }
algorithm 文章被收录于专栏
外源题解补充