読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

Indeedなう 予選A D:パズル

AtCoder

実際に参加して解けなかった問題です。
大事なことを二つほど学びました。

- 問題概要

H*Wのスライドパズルが与えられます。
このパズルを解くのに必要な最小の移動回数を答えよという問題です。
移動回数の最小値は24回以内であるという入力の制約が存在。

- 解法

基本方針は全探索です。
まずパズルの状態の保持の方法ですが、vectorに比較演算子が定義されているためmapのキーにvectorを保持することができます。
よってコスト及び既訪問の保持にはmapを使えます。一回の要素の追加、探索の計算量は(H*W*D)です。Dはパズルの移動回数。
このままBFSを行うと時間計算量、空間計算量がO(H*W*D*4^D),O(3^D)となるのでDの最大が24だとアウトです。
ここで重要となるテクニックに両側探索というものがあります。
両側探索はスタート、ゴールがともに一つで事前に分かっている問題に対して有効で、スタートからBFS,ゴールからBFSを行いぶつかったところが解になります。
これをするとスタートから深さ12のところまでBFS,同様にゴールから深さ12のところまでBFSを行い、ぶつかるところの深さの合計の最小値を求めればそれが解になります。
この方法を使うとDの最大が12となりギリギリ間に合います。
A*アルゴリズムを使っても通るらしいのですがテストケース次第では怪しいらしいので両側探索が安定だと思います。
状態の保存にハッシュを使うともっと高速になるかもしれないです。