3126 -- Prime Path - Logic Dice

3126 -- Prime Path
http://acm.pku.edu.cn/JudgeOnline/problem?id=3126

Prime minister(日本で言う総理大臣)が、prime number(素数)なルーム番号を欲しがる問題。以下、問題の概要と意訳。

4桁の素数(例えば1033, リーディングゼロは含まない)がPrime Ministerに元々与えられている部屋番号である。
しかし、セキュリティの問題から部屋番号を変えなければならなくなった。
Prime minister（以下P）「だが断る。我はPrime ministerだぞ！素数の番号以外の部屋番号なぞ付けられるか！」
「ですから、新しい素数の番号を用意しますから。ほら、8179なんてどうですか？」
P「我はPrime ministerだ。その部屋番号も完全で無くてはならん。最初の数値から、一つずつ数字を変えていき、最終的にその数字になるならよいだろう。もちろん、その途中の数字も素数で無くてはならん」

例えば上の例であれば、1033から始まり、8179に持って行く必要がある。そして、プログラムでは最低何回数字を変更すれば目的の数にたどり付けるかを出力する。
1033 -(0を7に)-> 1733 -(1を3に)-> 3733 -(3を9に)-> (略) -> 8779 -(7を1に)-> 8179
となり、この場合は6回の変更ですむので、出力は6となる。

以下、基本的な考え方とネタバレ。

この手の問題の基本である素数表をまずは作ります。まあ、1000以上10000未満の素数なんで、テーブルの作成はさっさと終わります。
次に、集合S1に最初の値を放り込みます。
S1から、1桁の数字の変更で生成できる、1000以上、10000未満の素数で、まだ出現していないものを全て生成し、集合S2に入れます。

この時点でS2に目的の数が出現すれば、1回で辿り着けることが分かります。出現しないのであれば、S1 <- S2とした後に、S2を空にしてこの処理を繰り返します。繰り返しとカウントをしていけば、何回で辿り着けるかは自ずと出てきます。
また、S2=φとなった時は辿り着けないということになります。

ソースは急ぎで書いたので、結構粗があります。かなりの最適化が可能でしょうが、Javaで391MSほどで解が出ているのでそれほど気にするところでも無いかと。
相変わらず、HashSet強いなぁ……記述が楽だ、本当。

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {

    boolean[] isPrime;
    boolean[] isAppeared;
    
    public static void main(String[] args) {
        new Main().run();
    }
    
    public void run() {
        isPrime = new boolean[10000];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for(int i = 2; i < isPrime.length; i++) {
            if( isPrime[i] ) {
                for(int j = 2*i; j < isPrime.length; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        Scanner s = new Scanner(System.in);
        isAppeared = new boolean[10000];
        HashSet<Integer> s1 = new HashSet<Integer>();
        HashSet<Integer> s2 = new HashSet<Integer>();
        for(int n = s.nextInt(); n > 0; n--) {
            int prime1 = s.nextInt();
            int prime2 = s.nextInt();
            
            Arrays.fill(isAppeared, false);
            s1.clear();
            s2.clear();
            
            s1.add(prime1);
            isAppeared[prime1] = true;
            int count = 0;
            if( prime1 != prime2 ) {
                while(true) {
                    s2.clear();
                    for(int num : s1) {
                        addNextNums(num, s2);
                    }
                    count++;
                    if( s2.contains(prime2) ) {
                        System.out.println(count);
                        break;
                    } else if( s2.isEmpty() ) {
                        System.out.println("Impossible");
                        break;
                    }
                    HashSet<Integer> tmp = s1;
                    s1 = s2;
                    s2 = tmp;
                }
            } else {
                System.out.println("0");
            }
        }
    }
    
    void addNextNums(int num, HashSet<Integer> s) {
        int[] code = toCode(num);
        for(int k = 0; k < 4; k++) {
            int save = code[k];
            for(int i = 0; i < 10; i++) {
                code[k] = i;
                int n = decode(code);
                if( isPrime[n] && !isAppeared[n] &&
                        1000 <= n && n <= 9999 ) {
                    isAppeared[n] = true;
                    s.add(n);
                }
            }
            code[k] = save;
        }
    }
    
    int[] toCode(int num) {
        int[] k = new int[4];
        int t = num;
        for(int i = 0; i < 4; i++) {
            k[i] = t%10;
            t /= 10;
        }
        return k;
    }
    
    int decode(int[] code) {
        int num = 0;
        int c = 1;
        for(int i = 0; i < 4; i++) {
            num += code[i] * c;
            c *= 10;
        }
        return num;
    }
    
}