POJ - 3278 - Catch That Cow(裸BFS)

题目链接

题意：

给定两个整数n和k，通过 n+1或n-1 或n*2 这3种操作，使得n==k，输出最少的操作次数

题解：

简单的对每个节点进行三个方向（三种走法）的BFS

AC代码：

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100005;
int vis[maxn];
int n,k;
int bfs(){
    queue<int>dq;
    dq.push(n);
    vis[n]=1;
    while(!dq.empty()){
        int x=dq.front();
        dq.pop();
        if(x+1>=0&&x+1<maxn&&vis[x+1]==0){
            dq.push(x+1);
            vis[x+1]=vis[x]+1;
            if(x+1==k)return vis[x+1];
        }
        if(x-1>=0&&x-1<maxn&&vis[x-1]==0){
            dq.push(x-1);
            vis[x-1]=vis[x]+1;
            if(x-1==k)return vis[x-1];
        }
        if(2*x>=0&&2*x<maxn&&vis[2*x]==0){
            dq.push(2*x);
            vis[2*x]=vis[x]+1;
            if(2*x==k)return vis[2*x];
        }
    }
}
int main(){
    scanf("%d%d",&n,&k);
    if(n>=k){
        printf("%d\n",n-k);
        return 0;
    }
    int ans=bfs();
    printf("%d\n",ans-1);

}