问题描述：略

思路： 简单的bfs，从初始位置开始，按位暴力从当前状态出发的所有素数状态，注意去重。这里因为数字不大于9999，所以我使用了vis[10000]来判断重复。

贴出代码

#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LOCAL
#define cls ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define Mod 998244353
#define ll long long int
#define mset(a,b) memset(a,b,sizeof(a))
#define INF 1e9
const int maxn=2e3+5;
int n,m;
char err[]="Impossible";
int vis[10005];
struct node{
    int x;
    int step;
};
bool isPrime(int x){
    int len=sqrt(x*1.0);
    for(int i=2;i<=len;i++){
        if(x%i==0) 
            return false;
    }
    return true;
}
int getInt(char *s){
    int x=0;
    for(int i=3;i>=0;i--){
        x=x*10+s[i]-'0';
    }
    return x;
}
int bfs(){
    mset(vis,0);
    queue<node> q;
    node st;
    st.x=n;
    st.step=0;
    q.push(st);
    node f;
    char tmp[10];
    char mp[10];
    vis[n]=1;
    while(!q.empty()){
        f=q.front();
        q.pop();
        if(f.x==m) return f.step;
        int x=f.x;
        for(int i=0;i<4;i++){
            mp[i]=x%10+'0';//取最后一位
            x/=10;
        }
        node ps;
        strcpy(tmp,mp);
        for(int i=0;i<10;i++){//个位变换 0~9
            tmp[0]='0'+i;
            int tp=getInt(tmp);
            if(isPrime(tp)&&!vis[tp]){
                vis[tp]=1;
                ps.x=tp;
                ps.step=f.step+1;
                q.push(ps);
            }
        }
        strcpy(tmp,mp);
        for(int i=0;i<10;i++){//十位变换 0~9
            tmp[1]='0'+i;
            int tp=getInt(tmp);
            if(isPrime(tp)&&!vis[tp]){
                vis[tp]=1;
                ps.x=tp;
                ps.step=f.step+1;
                q.push(ps);
            }
        }
        strcpy(tmp,mp);
        for(int i=0;i<10;i++){//百位变换 0~9
            tmp[2]='0'+i;
            int tp=getInt(tmp);
            if(isPrime(tp)&&!vis[tp]){
                vis[tp]=1;
                ps.x=tp;
                ps.step=f.step+1;
                q.push(ps);
            }
        }
        strcpy(tmp,mp);
        for(int i=1;i<10;i++){//千位变换 1~9
            tmp[3]='0'+i;
            int tp=getInt(tmp);
            if(isPrime(tp)&&!vis[tp]){
                vis[tp]=1;
                ps.x=tp;
                ps.step=f.step+1;
                q.push(ps);
            }
        }
    }
    return -1;
}
int main() {
    cls;
#ifdef LOCAL
    freopen("in.in","r",stdin);
#endif // LOCAL
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        int ans=bfs();
        if(ans==-1) cout<<err<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

睡前最后一题，可以开心的睡觉去了