POJ 3126: Prime Path

概要

2つの4桁の素数A, Bが与えられる．Aに対して，「どれか一つの桁を書き換えて別の素数にする（ただし，最上位は0に書き換えてはいけない）」という操作を最小何回行えばBにすることができるか．

解法

素数の表を作り，幅優先探索．

bool isntPrime[10000], visited[10000];
int main(){
    memset(isntPrime, 0, sizeof(isntPrime));
    for(int i = 2; i <= 9999; ++i){
        if(isntPrime[i]) continue;
        for(int j = i + i; j <= 9999; j += i)
            isntPrime[j] = true;
    }
    int T;
    scanf("%d", &T);
    for(--T; T >= 0; --T){
        int a, b, res;
        scanf("%d%d", &a, &b);
        queue<pair<int, int> > Q;

        res = -1;
        memset(visited, 0, sizeof(visited));
        Q.push(make_pair(a, 0));
        visited[a] = true;
        while(!Q.empty()){
            int t = Q.front().first, s = Q.front().second;
            Q.pop();
            if(t == b){
                res = s; break;
            }
            for(int i = 1; i <= 1000; i *= 10) for(int j = 0; j <= 9; ++j){
                if(i == 1000 && j == 0) continue;
                int nt = t + (j - t / i % 10) * i;
                if(visited[nt] || isntPrime[nt]) continue;
                visited[nt] = true;
                Q.push(make_pair(nt, s + 1));
            }
        }
        if(res == -1){
            printf("Impossible\n");
        }
        else{
            printf("%d\n", res);
        }
    }
    return 0;
}