POJ - 3126(BFS)

Prime Path

题目链接：

一只可爱的血小板为你引路啦~

题目：

题目意思：

给出两个四位数 a  b  要求从a 变换到 b ，且每次只变换一位数字且要求变换之后的四位数是素数  计算a 到 b 变换的次数

很容易想到bfs  但注意千位的时候不能为 0 

素数判断模板

AC代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <math.h>

using namespace std;
const int maxn  = 9999+5;
int t,n,m,vis[maxn];
struct node
{
    int x,step;
};
int judge_prime(int n)
{
    if(n==1)return 0;
    int i;  //此方法的含义是n如果不能被根号n之间的任何一个整数整除即为素数
    for(i = 2; i <= sqrt(n); i++) //sqrt() <math.h>函数库里的方法 开平方的意思
    {
        if(n % i ==0)
            return 0;
    }
    return 1;
}

void bfs()
{
    memset(vis,0,sizeof(vis));
    node b;
    b.x=n;
    b.step=0;
    vis[b.x]=1;
    queue <node> q;
    while(!q.empty())q.pop();
    q.push(b);
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(now.x==m)
        {
            printf("%d\n",now.step);
            return ;

        }
        for(int d=0; d<4; d++)
        {
            if(d==0)//个位
            {
                for(int i=1 ; i<=9 ; i+=2 )
                {
                    node next = now;
                    next.x = (now.x)/10*10 + i;
                    if(next.x!=now.x && !vis[next.x] && judge_prime(next.x))
                    {
                        vis[next.x]=1;
                        next.step++;
                        q.push(next);
                    }
                }
            }
            else if(d==1)//十位
            {
                for(int i=0 ; i<=9 ; i++)
                {
                    node next = now;
                    next.x = now.x/100*100 + i*10 + now.x%10;
                    if(next.x!=now.x && !vis[next.x] && judge_prime(next.x))
                    {
                        vis[next.x]=1;
                        next.step++;
                        q.push(next);
                    }
                }
            }
            else if(d==2)//百位
            {
                for(int i=0;i<=9;i++)
                {
                    node next = now;
                    next.x = now.x/1000*1000 + i*100 + now.x%100;
                    if(next.x!=now.x && !vis[next.x] && judge_prime(next.x))
                    {
                        vis[next.x]=1;
                        next.step++;
                        q.push(next);
                    }
                }
            }
            else if(d==3)
            {
                for(int i=1 ; i<=9 ; i++)
                {
                    node next = now;
                    next.x = i*1000 + now.x%1000;
                    if(next.x!=now.x && !vis[next.x] && judge_prime(next.x))
                    {
                        vis[next.x]=1;
                        next.step++;
                        q.push(next);
                    }
                }
            }
        }
    }
    printf("Impossible\n");
    return ;
}
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        bfs();
    }
    return 0;
}