AOJ 0121 Seven Puzzle

Jun 24, 2014  

幅優先探索の問題
まず考えたのは、初期状態から0をどんどん移動させて行く方法。
パズルの状態はstringで表現している。
mapで状態とそこまでの最短距離を対応させ、
mapに存在するかどうかでたどり着いたことがあるかを確認。
ただ、これだとTLEをくらう。

inputは1000個まで与えられるので、
毎回一から探索していっているのでは無駄が多い。
そもそも、ありえる状態は8!通りしかないから
そろった状態からたどりつけるすべての状態への最短距離を計算しておき
inputに対応した最短距離を出力するほうがいい。
同じようにmapを使って状態と最短距離を対応させる。

このエントリーをはてなブックマークに追加