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", n-k);

        else

            printf("%d\n", BFS(n, k));

    }

    return 0;

}