题目链接：传送门

题意：

给定两个四位数a。b,每次能够改变a的随意一位。而且确保改变后的a是一个素数。

问最少经过多少次改变a能够变成b.

分析：

BFS,每次枚举改变的数，有一个剪枝，就是假设这个改变的数之前已经得到过了，

就没有必要继续变回它了。

代码例如以下：

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <queue>

using namespace std;

struct nod{

    int a,b,c,d;

    int step;

    nod(){}

    nod(int _a,int _b,int _c,int _d):a(_a),b(_b),c(_c),d(_d){}

};

int l,r;

int vis[10010];

bool check(int x){

    for(int i=2;i*i<=x;i++)

        if(x%i==0) return false;

    return true;

}

bool isequal(nod tmp1,nod tmp2){

    if(tmp1.a==tmp2.a&&tmp1.b==tmp2.b&&tmp1.c==tmp2.c&&tmp1.d==tmp2.d)

        return true;

    return false;

}

void bfs(){

    queue<nod> Q;

    nod tmp,ans;

    tmp.a=l%10,l/=10;

    tmp.b=l%10,l/=10;

    tmp.c=l%10,l/=10;

    tmp.d=l%10;

    tmp.step=0;

    ans.a=r%10,r/=10;

    ans.b=r%10,r/=10;

    ans.c=r%10,r/=10;

    ans.d=r%10;

    Q.push(tmp);

    while(!Q.empty()){

        nod top = Q.front();

        Q.pop();

        if(isequal(top,ans)){

            printf("%d\n",top.step);

            return ;

        }

        for(int i=1;i<=9;i+=2){

            if(i!=top.a){

                tmp=nod(i,top.b,top.c,top.d);

                tmp.step=top.step+1;

                if(check(i+top.b*10+top.c*100+top.d*1000)&&!vis[i+top.b*10+top.c*100+top.d*1000]){

                    Q.push(tmp);

                    vis[i+top.b*10+top.c*100+top.d*1000]=1;

                }

            }

        }

        for(int i=0;i<=9;i++){

            if(i!=top.b){

                tmp=nod(top.a,i,top.c,top.d);

                tmp.step=top.step+1;

                if(check(i*10+top.a+top.c*100+top.d*1000)&&!vis[i*10+top.a+top.c*100+top.d*1000]){

                    Q.push(tmp);

                    vis[i*10+top.a+top.c*100+top.d*1000];

                }

            }

        }

        for(int i=0;i<=9;i++){

            if(i!=top.c){

                tmp=nod(top.a,top.b,i,top.d);

                tmp.step=top.step+1;

                if(check(i*100+top.b*10+top.a+top.d*1000)&&!vis[i*100+top.b*10+top.a+top.d*1000]){

                    Q.push(tmp);

                    vis[i*100+top.b*10+top.a+top.d*1000]=1;

                }

            }

        }

        for(int i=1;i<=9;i++){

            if(i!=top.d){

                tmp=nod(top.a,top.b,top.c,i);

                tmp.step=top.step+1;

                if(check(top.a+top.b*10+top.c*100+i*1000)&&!vis[top.a+top.b*10+top.c*100+i*1000]){

                    Q.push(tmp);

                    vis[top.a+top.b*10+top.c*100+i*1000]=1;

                }

            }

        }

    }

    puts("Impossible");

    return;

}

int main()

{

    int n;

    scanf("%d",&n);

    while(n--){

        scanf("%d%d",&l,&r);

        memset(vis,0,sizeof(vis));

        bfs();

    }

    return 0;

}