空间最短路径，BFS(POJ3278)

题目链接：http://poj.org/problem?id=3278

#include <cstdio>

#include <queue>

#include <string.h>

using namespace std;

#define MAXN 200000

int key[MAXN];///走到key[i]的步数

bool vis[MAXN];///是否走过

int bfs(int first,int last)

{

    int v;

    queue<int>q;

    ///初始化没有走过

    memset(vis,false,sizeof(vis));

    q.push(first);

    key[first]=;

    vis[first]=true;

    while(!q.empty())

    {

        v=q.front();

        q.pop();

        if(v==last)

            return key[v];

        ///向左走

        if((v-)>=&&(v-)<MAXN&&!vis[v-])

        {

            key[v-]=key[v]+;

            vis[v-]=true;

            q.push(v-);

        }

        ///向右走

        if((v+)>=&&(v+)<MAXN&&!vis[v+])

        {

            key[v+]=key[v]+;

            vis[v+]=true;

            q.push(v+);

        }

        ///跳

        if((v*)>=&&(v*)<MAXN&&!vis[v*])

        {

            key[v*]=key[v]+;

            vis[v*]=true;

            q.push(v*);

        }

    }

}

int main()

{

    int n,k;

    while(scanf("%d%d",&n,&k)!=EOF)

    {

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

    }

    return ;

}