POJ 3126 - Prime Path - [线性筛+BFS]

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

题意：

给定两个四位素数 $a,b$，要求把 $a$ 变换到 $b$。变换的过程每次只能改动一个数，要保证每次变换出来的数都是一个没有前导零的四位素数。

要求每步得到的素数都不能重复，求从 $a$ 到 $b$ 最少需要变换多少步；如果无法达到则输出Impossible。

题解：

在BFS之前先用线性筛筛出 $10000$ 以内的素数，方便后面判断是否为素数。

剩下的就是从 $a$ 为起点，入队并标记已经出现过。每次队列非空就取出队头，尝试把这个数的每一位全部改一编，是素数且没出现过的就入队并标记。

循环往复，直到到达 $b$；或者队列空了还没找到。

AC代码：

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

typedef pair<int,int> pii;

int st,ed;

/************************** 线性筛 - st **************************/

const int MAX=;

int cnt,prime[MAX+];

bool isPrime[MAX+];

void Screen() //欧拉筛法求素数

{

    cnt=;

    memset(isPrime,,sizeof(isPrime));

    isPrime[]=isPrime[]=;

    for(int i=;i<=MAX;i++)

    {

        if(isPrime[i]) prime[cnt++]=i;

        for(int j=;j<cnt;j++)

        {

            if(i*prime[j]>MAX) break;

            isPrime[i*prime[j]]=;

            if(i%prime[j]==) break;

        }

    }

}

/************************** 线性筛 - ed **************************/

queue<pii> Q;

bool vis[MAX+];

int bfs()

{

    memset(vis,,sizeof(vis));

    while(!Q.empty()) Q.pop();

    Q.push(make_pair(st,));

    vis[st]=;

    while(!Q.empty())

    {

        pii now=Q.front(); Q.pop();

        if(now.first==ed) return now.second;

        for(int i=;i<=;i++) //千位

        {

            int k=now.first/;

            if(k==i) continue;

            pii nxt=make_pair(now.first-k*+i*,now.second+);

            if(isPrime[nxt.first] && !vis[nxt.first])

            {

                Q.push(nxt);

                vis[nxt.first]=;

            }

        }

        for(int i=;i<=;i++) //百位

        {

            int k=(now.first%)/;

            if(k==i) continue;

            pii nxt=make_pair(now.first-k*+i*,now.second+);

            if(isPrime[nxt.first] && !vis[nxt.first])

            {

                Q.push(nxt);

                vis[nxt.first]=;

            }

        }

        for(int i=;i<=;i++) //十位

        {

            int k=(now.first%)/;

            if(k==i) continue;

            pii nxt=make_pair(now.first-k*+i*,now.second+);

            if(isPrime[nxt.first] && !vis[nxt.first])

            {

                Q.push(nxt);

                vis[nxt.first]=;

            }

        }

        for(int i=;i<=;i++) //个位

        {

            int k=now.first%;

            if(k==i) continue;

            pii nxt=make_pair(now.first-k+i,now.second+);

            if(isPrime[nxt.first] && !vis[nxt.first])

            {

                Q.push(nxt);

                vis[nxt.first]=;

            }

        }

    }

    return -;

}

int main()

{

    Screen();

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&st,&ed);

        int ans=bfs();

        if(ans==-) printf("Impossible\n");

        else printf("%d\n",ans);

    }

}