POJ 3126 Prime Path 簡單廣搜(BFS)，pojbfs

POJ 3126 Prime Path 簡單廣搜(BFS)，pojbfs

題意：一個四位數的質數，每次只能變換一個數字，而且變換後的數也要為質數。給出兩個四位數的質數，輸出第一個數變換為第二個數的最少步驟。

利用廣搜就能很快解決問題了。還有一個要注意的地方，千位要大於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;
}