1646. Prime Path

#include<bits/stdc++.h>
#define MAX 10000
using namespace std;
typedef pair<string,int> P;
string n,m;
void bfs();
int t,sign[MAX],pri[MAX];//sign标记数是否被用过
int main()
{
    for(int i=2;i<MAX;i++)
        for(int j=i;i*j<MAX;j++)
        pri[i*j]=1;
    cin>>t;
    while(t--)
    {
        fill(sign,sign+MAX,0);
        cin>>n>>m;sign[atoi(n.c_str())]++;
        bfs();
    }
}
void bfs()
{
    queue<P>pq;
    string x;int step;
    pq.push({n,0});
    while(!pq.empty())
    {
        P p=pq.front();
        pq.pop();
        x=p.first;step=p.second;
        if(x==m)
        {
            printf("%d\n",step);
            return ;
        }
        for(int i=0;i<=3;i++)
            for(int j=0;j<=9;j++)
        if(!(i==0&&j==0))//千位数字不能为0
        {
            string str=x;str[i]='0'+j;
            if(str!=x&&!sign[atoi(str.c_str())]&&!pri[atoi(str.c_str())])//若变换后数字不想等且未使用过且为素数
            {
                sign[atoi(str.c_str())]++;
                pq.push({str,step+1});
            }
        }
    }
    puts("Impossible");
}