POJ 3278 BFS + queue

杨鹏伟

发布于 2020-09-10 23:57:47

4110

发布于 2020-09-10 23:57:47

文章被收录于专栏：ypwypw

农夫知道一头牛的位置，想要抓住它。农夫和牛都于数轴上，农夫起始位于点N(0<=N<=100000) ，牛位于点K(0<=K<=100000) 。农夫有两种移动方式： 1、从X移动到X-1或X+1 ，每次移动花费一分钟； 2、从X移动到2*X ，每次移动花费一分钟；假设牛没有意识到农夫的行动，站在原地不动。最少要花多少时间才能抓住牛？ Input 一行:以空格分隔的两个字母: N和 K Output 一行: 农夫抓住牛需要的最少时间。 Sample Input 5 17 Sample Output 4 Hint 农夫使用最短时间抓住牛的方案如下: 5-10-9-18-17, 需要4分钟.

#include<bits/stdc++.h>
using namespace std;
#define N 100010
int step[N],vis[N];
queue<int>q;
int bfs(int n,int k){
    int now,next;
    step[n]=0;
    vis[n]=1;
    q.push(n);
    while(!q.empty()){
        now=q.front();
        q.pop();
        for(int i=0;i<3;i++){
            if(i==0) next=now-1;
            else if(i==1) next=now+1;
            else if(i==2) next=now*2;
            if(next<0||next>N) continue;
            if(!vis[next]){
                vis[next]=1;
                q.push(next);
                step[next]=step[now]+1; 
            }
            if(next==k) return step[next];
        }
    }
}
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    if(n>=k) printf("%d\n",n-k);  
    else printf("%d\n",bfs(n,k));
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-04-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除

input