HPPPPPPPPPPPP

競技プログラミングの解法置き場

Indeedなう(予選A) D - パズル

問題

atcoder.jp

 

キーワード

BFS 枝刈り 優先度付きキュー 

 

解法

このようなパズルの最短手順は、盤面を頂点、操作を重み無しの辺 とすることで、BFS(幅優先探索)で解くことが出来る。

 

例えば、H=2,W=2の場合以下のようになり、最短手順は6である。

 

f:id:HAPPAx:20210323191848j:plain


盤面の数は(遷移先)^(操作回数)であり、今回は操作回数が24回以内である事が保証されているため、盤面の数は3^24≒3×10^11となる。遷移先は4つだが、戻る操作は明らかに無駄なため遷移先は3つと見なせる。これは実行時間制限の4秒に間に合わない。

 

ここで、「0を除く各マスの本来のマスの位置と現在のマスの位置のマンハッタン距離の合計」と「現在の操作回数」の合計をコストと呼ぶ。コストが25以上であれば、その盤面からどう操作しようと24手以内に盤面は完成しない。また、コストが大きくなる盤面よりも、小さくなる盤面に優先的に遷移した方が良い。

 

以上のことから、現在のコストが25以上の盤面からの遷移は無視し、かつコストが小さい盤面から優先的に遷移し、完成盤面になった時点で操作を打ち切る事で、大幅に計算量を小さくすることが出来る。

 

実装上の注意

優先度付きキューを使えば、コストが小さい盤面から順に遷移する事が出来る。

チェック済み盤面の判定は、仮想配列を使えばよい。 

 

ACコード

 

atcoder.jp

 

類題

atcoder.jp

 

感想

枝刈りすごい。

これをダイクストラに落とし込んだアルゴリズムをA*(エースター)探索と呼ぶらしい。