cdoj 851 方老师与素数 bfs

时间：2023-03-08 21:13:35

方老师与素数

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

方老师最近很喜欢素数，他想玩一个游戏：

现在有两个44位的素数nn和mm，你一次可以改变nn的一位数字，并且改变过后的新数字必须也是个素数，并且也不能有前导00。请问使nn变为mm最少需要多少步。

例如n=1033n=1033 m=8179m=8179

那么可行的变化是：

1033

1733

3733

3739

3779

8779

8179

Input

第一行有一个整数T(T≤100)T(T≤100)，代表测试数据的组数。

对于每组数据，每行有两个44位素数N，MN，M（没有前导00）

Output

对于每一组数据,如果能够得到mm，输出最少的步数，否则输出Impossible

Sample input and output

Sample Input Sample Output 
3

1033 8179

1373 8017

1033 1033
 
6

7

0

Source

2014 UESTC Training for Search Algorithm
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

#define eps 1e-14

const int N=2e5+,M=1e6+,inf=1e9+,mod=1e9+;

const ll INF=1e18+;

int p[];

int prime(int n)

{

    if(n<=)

    return ;

    if(n==)

    return ;

    if(n%==)

    return ;

    int k, upperBound=n/;

    for(k=; k<=upperBound; k+=)

    {

        upperBound=n/k;

        if(n%k==)

            return ;

    }

    return ;

}

int check(int x,int y)

{

    int sum=;

    while(x)

    {

        if(x%!=y%)sum++;

        x/=;

        y/=;

    }

    return sum;

}

int flag[];

struct is

{

    int num;

    int ans;

    is(){}

    is(int x,int y)

    {

        num=x;

        ans=y;

    }

};

int main()

{

    int cnt=;

    for(int i=;i<=;i++)

    if(prime(i))

    p[cnt++]=i;

    int T;

    scanf("%d",&T);

    while(T--)

    {

        for(int i=;i<cnt;i++)

            flag[p[i]]=;

        int n,m;

        scanf("%d%d",&n,&m);

        flag[n]=;

        queue<is>q;

        q.push(is(n,));

        int out=inf;

        while(!q.empty())

        {

            is v=q.front();

            q.pop();

            if(v.num==m)

            {

                out=v.ans;

                break;

            }

            for(int i=;i<cnt;i++)

            {

                if(!flag[p[i]]&&check(v.num,p[i])==)

                {

                    flag[p[i]]=;

                    q.push(is(p[i],v.ans+));

                }

            }

        }

        if(out!=inf)

        printf("%d\n",out);

        else

            printf("Impossible\n");

    }

    return ;

}

相关文章