#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

const int maxn=10010;
bool vis[maxn];
int d[maxn];
int st,ed;

bool isprime(int n){
    if(n<=1)    return false;
    int sqr=(int)sqrt(1.0*n);
    for(int i=2;i<=sqr;i++){
        if(n%i==0)
            return false;
    }
    return true;
}

int a[4];
void toarray(int n){
    int cnt=0;
    while(n){
        a[cnt++]=n%10;
        n/=10;
    }
    reverse(a,a+4);
}

int toint(){
    int res=0;
    for(int i=0;i<4;i++){
        res=res*10+a[i];
    }
    return res;
}

void BFS(int st){
    queue<int> q;
    q.push(st);
    while(!q.empty()){
        int top=q.front();
        q.pop();
        toarray(top);
       if(top==ed)
            return ;
        for(int i=0;i<10;i++){
            for(int j=0;j<4;j++){
                if(i!=a[j]){
                    int tmp=a[j];
                    a[j]=i;
                    int tmpres=toint();
                    if(!isprime(tmpres)||vis[tmpres]==true){
                        a[j]=tmp;
                        continue;
                    }
                    d[tmpres]=d[top]+1;
                    q.push(tmpres);
                    a[j]=tmp;
                    vis[tmpres]=true;
                }
            }
        }
    }
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        fill(vis,vis+maxn,false);
        fill(d,d+maxn,0);
        scanf("%d%d",&st,&ed);
        BFS(st);
        printf("%d\n",d[ed]);
    }
    return 0;
}

• Re:样例过了，但是A不了，有提供样例的大佬吗？ (1809) lichuhang 2019-07-01 18:21:35