AOJ 0179
とある記事を見ていたらAOJ0179 Mysterious Wormというのを見つけたので考えてみました。
解法
問題の詳細は↑のリンク先を見て頂くとして、最短手数を求めるということなので幅優先探索で実装してみました。
求められているのは最短手数だけなのですが、せっかくなのでその最短手数で虫の色の変遷も見てみたいのでそれも追えるように考えてみます。
データ構造
色の管理
今回のルールとして下記2点があります。
-
色が変わるのは、隣り合っている色違いの 2つの体節のペア 1組だけが変わり、他の体節の色 は変わらない。ただし、そのようなペアが複数あるときに、どのペアの色が変わるかはあらか じめ予測できない。
-
そのようなペアは、2つの体節の色のどちらでもない色に同時に変わる(たとえば、緑と赤の体 節が隣り合っているときは、それらが同時に青に変わる)。
色が変わるパターンでの隣り合う体節について、赤をR,緑をG,青をBとして、
「体節xの色 体節x+1 => 変化する色」と表記するとすると下記6パターンがあります。
R G => B
G R => B
R B => G
B R => G
G B => R
B G => R
とすると、仮に、R,G,Bそれぞれに2進数で
R = 0b001
G = 0b010
B = 0b100
という値を割り当て、全BITが立っている状態を
ALL_COLOR = R | G | B
とすると、上記のパターンは
ALL_COLOR ^ (色1 | 色2)
とすることで、色3が求められます。
状態の管理
幅優先探索なので深さ優先探索のように一つ前の状態が遷移元とはいえないので、定番ですがキューに入れる状態に「その状態になった前の状態」へのポインタを入れておきます。
このため、キュー管理する状態として「その手順の状態＋その手順になる前の状態へのポインタ」を持つHistoryを設けました。
またすでに発生した状態のチェックとHistoryにいれる状態を効率よく管理するために、状態から一意に決まる整数値をHash値として計算しその整数値から状態を復元したり、すでに発生した状態をチェックできるようにしました。
具体的には
状態：[R G B R R]
というであったとき、これらの各要素は2進数で、
状態[001, 010, 100, 001, 001]
となります。
このため、これらをつなげたbit列を一つの整数とみなすと各状態につき001010100001001というような一つの整数が一意に決まるのでこれは「状態からハッシュ値への完全ハッシュ関数」が作ることができることになります。(最小完全ハッシュ関数ではありません。)
今後状態をwormと表現すると、この完全ハッシュ関数は
private int calcWormHash(List<Integer> worm) {
int hash = 0;
for (int w: worm) {
hash = (hash << 3) | w;
}
return hash;
}
と実装できます。またhash値からwormを復元するためには、上記の逆を行って、
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;
}
と実装できます。
このハッシュ値を使って前述した、「その手順の状態＋その手順になる前の状態へのポインタ」を持つHistoryは
その手順への状態をwormHash, その手順になる前の状態へのポインタをprevとして
class History {
private int wormHash;
private History prev;
}
と実装できます。
探索
上記までに定義したデータ構造を使うと実際の探索処理は
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)を返す
}
}
で、解が見つかった場合、最終状態のHistoryが返されます。
Historyから手数や手順を計算、復元するのは省略します。
これで例えばサンプルの一つ gbrggrbggrだと、下記のような結果が得られます(提出用は手数だけの出力)
gbrggrbggr
rrrggrbggr
rrrgbbbggr
rrrrrbbggr
rrrrrbrrgr
rrrrrggrgr
rrrrrgbbgr
rrrrrrrbgr
rrrrrrrrrr
8
結果
AOJは初めて提出したのでちょっとsubmitにもたついてしまいました。。
なんだかメモリの量が設定値より多い気がするんですが、Acceptになってたら正解なんでしょうか？？
ソース全体は
https://gist.github.com/pocari/fa74db3c391ae3e072b7
です。