首页 > > 程序设计 > C/C++ >

POJ 3126 Prime Path 简单广搜(BFS)

2018-06-17 23:54:11来源：未知阅读 ()

题意：一个四位数的质数，每次只能变换一个数字，而且变换后的数也要为质数。给出两个四位数的质数，输出第一个数变换为第二个数的最少步骤。

利用广搜就能很快解决问题了。还有一个要注意的地方，千位要大于0。例如0373这个数不符合要求。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <map>
using namespace std;

struct Struct
{
    int num;
    int step;
};
bool Prime(int a) //判断是否为质数
{
    for(int i=2;i<=sqrt(a);i++)
        if(a%i==0)
            return false;
    return true;
}
int bfs(int a,int b)
{
    queue<Struct>q;
    map<int,bool>m; //用map来标记数字是否被访问过
    Struct temp,next;
    temp.num=a;
    temp.step=0;
    m[a]=true;
    q.push(temp);
    while(!q.empty())
    {
        temp=q.front();
        if(temp.num==b)
            return temp.step;
        q.pop();
        for(int i=1;i<10;i++) //变换千位
        {
            next=temp;
            next.num=next.num%1000+i*1000;
            if(!m[next.num] && Prime(next.num))
            {
                m[next.num]=true;
                next.step++;
                q.push(next);
            }
        }
        int x=100;
        for(int i=0;i<3;i++) //变换百位，十位，个位
        {
            for(int j=0;j<10;j++)
            {
                next=temp;
                next.num=next.num%x+j*x+next.num/(x*10)*(x*10);
                if(!m[next.num] && Prime(next.num))
                {
                    m[next.num]=true;
                    next.step++;
                    q.push(next);
                }
            }
            x=x/10;
        }
    }
    return -1;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        int ans=bfs(a,b);
        if(ans!=-1)
            printf("%d\n",ans);
        else
            printf("Impossible\n");
    }
    return 0;
}