题解

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N=1e5+10;
bool st[N],su[N];    
struct xxx             
{
    int w;
    int d;
};
int xx(int x)           
{
    if(x==1)    return 0;
    for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)  return 0;
    }
    return 1;
}
void bfs(int a,int b)
{
    memset(st,false,sizeof(st));   
    queue<xxx> q;
    q.push({a,0});
    st[a]=true;
    while(q.size())
    {
        xxx z=q.front();
        q.pop();
        if(z.w==b)           
        {
            cout << z.d << endl;
            return ;
        }
        int a1=z.w%10;
        int a2=z.w/10%10;
        int a3=z.w/100%10;
        int a4=z.w/1000;
        for(int i=0;i<=9;i++)          
        {
            int y=a4*1000+a3*100+a2*10+i;
            if(y==z.w)  continue;
            else
            {
                if(!st[y]&&su[y])
                {
                    q.push({y,z.d+1});
                }
            }
        }
        for(int i=0;i<=9;i++)       
        {
            int y=a4*1000+a3*100+i*10+a1;
            if(y==z.w)  continue;
            else
            {
                if(!st[y]&&su[y])
                {
                    q.push({y,z.d+1});
                    st[y]=true;
                }
            }
        }
        for(int i=0;i<=9;i++)
        {
            int y=a4*1000+i*100+a2*10+a1;
            if(y==z.w)  continue;
            else
            {
                if(!st[y]&&su[y])
                {
                    q.push({y,z.d+1});
                    st[y]=true;
                }
            }
        }
        for(int i=1;i<=9;i++)       
        {
            int y=i*1000+a3*100+a2*10+a1;
            if(y==z.w)    continue;
            else
            {
                if(!st[y]&&su[y])
                {
                    q.push({y,z.d+1});
                    st[y]=true;
                }
            }
        }
    }
    cout << "-1" << endl;   
    return ;
}
int main()
{
    for(int i=1000;i<=9999;i++) 
    {
        if(xx(i)==1)
            su[i]=true;
        else
            su[i]=false;
    }
    
    int n;
    cin >> n;
    while(n--)
    {
        int a,b;
        cin >> a >> b;
        bfs(a,b);
    }
    return 0;
}