POJ 3126 Prime Path (BFS+剪枝)

POJ 3126 Prime Path (BFS+剪枝)

題目鏈接：傳送門

題意：

給定兩個四位數a，b,每次可以改變a的任意一位，並且確保改變後的a是一個素數。

問最少經過多少次改變a可以變成b.

分析：

BFS,每次枚舉改變的數，有一個剪枝，就是如果這個改變的數之前已經得到過了，

就沒有必要繼續變回它了。

代碼如下：

#include 
#include 
#include 
#include 
#include 
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 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;
}