AOJ0179 Mysterious Worm ref: http://qiita.com/pocari/items/d1bbb48b8e8fe32fe2f2

calcWormHash

    private int calcWormHash(List<Integer> worm) {
        int hash = 0;

        for (int w: worm) {
            hash = (hash << 3) | w;
        }

        return hash;
    }

file0.txt

R G => B
G R => B
R B => G
B R => G
G B => R
B G => R

file1.txt

R = 0b001
G = 0b010
B = 0b100

file10.txt

gbrggrbggr
rrrggrbggr
rrrgbbbggr
rrrrrbbggr
rrrrrbrrgr
rrrrrggrgr
rrrrrgbbgr
rrrrrrrbgr
rrrrrrrrrr
8

file2.txt

ALL_COLOR = R | G | B

file3.txt

ALL_COLOR ^ (色1 | 色2)

file4.txt

状態：[R G B R R]

file5.txt

状態[001, 010, 100, 001, 001]

History

class History {
    private int wormHash;
    private History prev;
}

wormHashToWorm

    private List<Integer> wormHashToWorm(int wormHash) {
        List<Integer> worm = new ArrayList<Integer>();

        while (wormHash > 0) {
            worm.add(0, wormHash & ALL_COLOR);
            wormHash = wormHash >> 3;
        }

        return worm;
    }

探索処理(擬似コード)

public History solve(wormの初期状態) {
   int 初期状態のハッシュ = calcWormHash(wormの初期状態);

   Set<Integer> すでに発生した状態を管理するためのキャッシュ;
   Queue<History> 探索用キュー

   while (探索用キューが空でない間) {
     History 探索対象状態 = キューから状態を取得

     if (すべて体節が同じ色?) {
         //今の状態が解なので探索終了
         return 探索対象状態
     } else {
         for (探索対象状態の内,隣り合う体節のインデックスi, jをすべて試す) {
　　　　　　　if (隣り合う体節i, jの色が違う?) {
                int 変化後の色 = ALL_COLOR ^ (色i | 色J)
                体節i, jの色を 変化後の色 にする
                if (変化後の状態のハッシュ値がまだキャッシュにない?) {
                   新しい局面が見つかったのでキューに追加
                }
                次のi, jのために 変化後の色 を取り消すして元の色に戻す
            }
         }
     }
     return 見つからなかったので失敗(null)を返す
   }
}