kuangbin帶你飛專題:poj3278
題目含義：給你N，M，用N-1，N+1，N2的三種方式找出經(jīng)過若干次跳躍變?yōu)镸的最小次數(shù)。例如5->17,如圖。

討論

解答樹

#include <cstdio>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int N, M;
const int maxn=200000;
int dis[maxn];
int vis[maxn];
int bfs()
{
    queue<int> que;
    que.push(N);
    vis[N]=1;
    if(N==M)return 0;
    while(!que.empty())
    {
        int x=que.front();
        que.pop();
        int nx=x+1, ny=x*2, nz=x-1;
        if(nx==M||ny==M||nz==M)
        return dis[x]+1;
        else {
            if(nx<=2*max(M, N)&&nx>=0&&!vis[nx])
            {
                vis[nx]=1;
                que.push(nx);
                dis[nx]=dis[x]+1;
            }
            if(ny<=2*max(M, N)&&ny>=0&&!vis[ny])
            {
                vis[ny]=1;
                que.push(ny);
                dis[ny]=dis[x]+1;
            }
            if(nz<=2*max(M, N)&&nz>=0&&!vis[nz])
            {
                vis[nz]=1;
                que.push(nz);
                dis[nz]=dis[x]+1;
            }
        }
    }
    return -1;
}
int main(void)
{
    while(scanf("%d%d", &N, &M)!=EOF)
    {
        memset(vis, 0, sizeof(vis));
        memset(dis, 0, sizeof(dis));
        int res=bfs();
        printf("%d\n", res);
    }
    return 0;
}