F - Prime Path

时间:2023-12-23 18:54:55
题目大意:
素数路径
估计看数据就明白这道题什么意思了......给两个素数,都是四位数的素数,并且没有前导0,现在需要经过一种变换把一个素数转换成另一个,当然这种转换是有规则的,规则就是每次只能改变这个四位数的其中一位数字,当然改变后的数字也得是素数,问最少的改变次数是多少......
貌似还是广搜..............................................................................................不过做起来应该会麻烦点,要求素数,不过可以搞一个素数表这样判断起来更方便
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std; #define maxn 10000 int p[maxn];//标记4位数的素数 int Prime(int n)
{
    int i, k=sqrt(n);     for(i=; i<=k; i++)
        if(n % i == )
            return ;     return ;
}
int Turn(int n, int k)//把n的第k位转换成0
{
    char s[]={};     sprintf(s, "%d", n);
    s[k] = '';
    sscanf(s, "%d", &n);     return n;
}
int BFS(int s, int e)
{
    int i, j, k, q;
    int v[maxn]={};
    queue<int> Q;     Q.push(s);
    v[s] = ;     while(Q.size())
    {
        s = Q.front();Q.pop();         if(s == e)
            return v[s]-;         int t = ;         for(i=; i<; i++)
        {
            q = Turn(s, i);             for(k=; k<; k++)
            {
                j = q+k*t;                 if(p[j] ==  && v[j] == )
                {
                    Q.push(j);
                    v[j] = v[s] + ;
                }
            }             t /= ;
        }
    }     return -;
} int main()
{
    int i, s, e, T;     for(i=; i<maxn; i++)
        p[i] = Prime(i);     scanf("%d", &T);     while(T--)
    {
        scanf("%d%d", &s, &e);         int ans = BFS(s, e);         if(ans == -)
            printf("Impossible\n");
        else
            printf("%d\n", ans);
    }     return ;

}