题目描述：给出一个素数，要求通过变换这个素数的某个数字，使变换后的数字仍然是素数，要求变换到给定的一个素数停止，求最少的变化次数。

解题分析：bfs模拟求最短路就行。把每个数当做图中的一个点。

代码入下：

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

const int maxn=10000+10;
const int INF=0x3f3f3f3f;
int prime[maxn],dist[maxn];

bool bfs(int st,int ed)
{
    queue< int > q;
    q.push(st);
    while(!q.empty())
    {
        int temp=q.front();
        q.pop();
        if(temp==ed)
        {
            dist[ed]=dist[temp];
            return true;
        }
        int a=temp/1000,b=temp%1000/100,c=temp%100/10,d=temp%10;
        int num;
        for(int i=0;i<4;i++)//下面枚举可能的路径
        {
            for(int j=0;j<=9;j++)
            {
                if(i==0) num=j*1000+b*100+c*10+d;
                else if(i==1) num=a*1000+100*j+c*10+d;
                else if(i==2) num=a*1000+b*100+j*10+d;
                else if(i==3) num=a*1000+b*100+c*10+j;
                if(num>=1000&&num<9999&&!prime[num]&&dist[num]==INF)
                {
                    dist[num]=dist[temp]+1;
                    q.push(num);
                }
            }
        }
    }
    return false;
}

int main()
{
    memset(prime,0,sizeof(prime));
    int k=sqrt(10000+0.5);
    for(int i=2;i<=k;i++)//素数打表
    {
        if(!prime[i])
        {
            for(int j=i*i;j<=10000;j+=i)
                prime[j]=1;
        }
    }
    int kase;
    scanf("%d",&kase);
    while(kase--)
    {
        int st,ed;
        scanf("%d %d",&st,&ed);
        memset(dist,0x3f,sizeof(dist));
        dist[st]=0;
        if(bfs(st,ed)) printf("%d\n",dist[ed]);
        else printf("Impossible\n");
    }
    return 0;
}

Prime Path POJ - 3126

全站热榜