题目传送门：

这里

题目大意：给你一个开始的素数m，后来给你一个素数n，问m可不可以每一次只变换一个数字，使得可以从m变到n，并且在过程中变到的每一个数字都为素数，求最少变换次数。

这种题目设计到求最短路径那么肯定需要用到BFS，然后我们建立思路：

 

第一步：素数打表，打完表之后我们就可以知道，1000-10000中有哪些素数，就可以进行判定。

第二步：每一个数可以到达的状态，即他们通过变换一个数字得到的素数有哪些，然后继续让这些素数去变另一个素数。

第三步：我们只需要判断当 队列的首端是 要变到的那个数时，我们就返回到达它的次数就可以了，一定是最小！（BFS的性质）

 

需要准备的东西:

1.dis数组用来标记由m到达 他能转化到 每一个素数 的 最少次数。

2.vis数组，与prime数组 用来素数打表。

3.vis1数组标记一下这个素数已经 被访问过，无需再次访问，因为再次访问绝对没有第一次的次数少。

 

其实，这个题目 还有一种 算是挺棒的缩内存的方法吧，可以用一个结构体 将数据 离散化，要步如果你要标记一个很大的素数访问过没有，你的标记数组会需求很大，所以我们可以 将1000-10000内的素数排序从小到大，然后让他们对应着 每一个数值（1-N），因为素数不可能会有重复，所以创建的这个映射也不会有重复，所以我们只需要把数组开到 1000-10000内素数的个数就可以了。在这里我没有用这种方法，为了让 包括我在内的小白们好理解。那直接附上代码+注释：

#include <queue>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
const int mod=10007;
const int INF=0x3f3f3f3f;
const int maxn=1e6+5;
bool vis[10005];
int prime[10005];
bool vis1[10005];//标记素数走过了
int dis[10005];//素数路径
int cnt=0;
int st,ed;
int pr1,pr2;//初始素数，结束素数
void set_prime()//素数打表
{
    memset(vis,false,sizeof(vis));
    for(int i=2;i<10005;i++)
    {
        if(vis[i]==false) prime[++cnt]=i;
        for(int k=1;k<=cnt&&i*prime[k]<10005;k++)
        {
            vis[i*prime[k]]=true;
            if(i%prime[k]==0) break;
        }
    }
    for(int i=1;i<=cnt;i++)//打完表之后，更新1000以上的开始数值
        if(prime[i]>=1000)
        {
            st=i;
            break;
        }
}
bool check(int x,int y)//用来判断是否只有一位不同，如果只有一位不同，才可以变过去。
{
    int cot=0;
    for(int i=1;i<=4;i++)
    {
        if(x%10==y%10) cot++;
        x/=10;y/=10;
    }
    if(cot==3) return true;
    return false;
}
int bfs()
{
    queue<int>q;
    memset(vis1,false,sizeof(vis1));
    q.push(pr1);
    vis1[pr1]=true;
    dis[pr1]=0;
    while(!q.empty())
    {
        int pre=q.front();q.pop();
        if(pre==pr2) return dis[pre];
        for(int i=st;i<=cnt;i++)
        {
            int z=prime[i];
            if(check(z,pre)==true&&vis1[z]==false)//判断一下再push就好了
            {
                dis[z]=dis[pre]+1;
                vis1[z]=true;
                q.push(z);
            }

        }
    }
    return -1;//有可能找不到
}
int main()
{
    int T;
    set_prime();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&pr1,&pr2);
        int ans=bfs();
        if(ans==-1) printf("Impossible\n");
        else printf("%d\n",ans);
    }
    return 0;
}

这个代码的复杂度，略高由于数据的范围最坏的情况应在再1e6.5左右，如果还有更简洁的更快速的方法，欢迎提出一起交流加油！