BFS(广度优先搜索) poj3278

***今天发现一个很有趣的是，这道题应该几个月前就会了，但是一次比赛中总是WA，果断C++提交，然后就过了，然后就很无语了，G++不让过C++能过，今天又交一遍发现把队列定义为全局变量就都能过了，至于原理，不懂....***

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<algorithm>

using namespace std;
typedef long long LL;
#define N 101000
#define INF 0x3f3f3f

int vis[N], step[N];
queue<int> q;

int BFS(int n, int k)
{
    
    int a, b;
    q.push(n);
    memset(vis, 0, sizeof(vis));
    memset(step, 0, sizeof(step));
    vis[n]=1;
    step[n]=0;

    while(!q.empty())
    {
        a=q.front();
        q.pop();
        if(a==k)
            return step[a];
        for(int i=1; i<=3; i++)
        {
            if(i==1)
                b=a-1;
            else if(i==2)
                b=a+1;
            else
                b=a*2;
            if(b<0 || b>100000)
                continue;
            if(!vis[b])
            {
                vis[b]=1;
                step[b]=step[a]+1;
                q.push(b);
            }
        }
    }
}

int main()
{
    int n, k;

    while(~scanf("%d%d", &n, &k))
    {
        while(!q.empty())
            q.pop();
        if(n>=k)
            printf("%d
", n-k);
        else
            printf("%d
", BFS(n, k));
    }
    return 0;
}