Indeedなう（予選A）2015 D - パズル

問題：D - パズル

解答①：Submission #14186203 - Indeedなう（予選A）

解法①：最小手数が24手以内という上限があるため、これをうまく使う。
半分全列挙の応用。最初の盤面から12手以内で到達できる盤面とその盤面に到達する最小手数のmap(mp)、最後の盤面から12手以内で到達できる盤面とその盤面に到達する最小手数のmap(mp2)を準備する。
mpの各要素について(key = kとする)、mp2にその盤面があれば、mp[k] + mp2[k]の最小値が答え。

解答②：Submission #14204270 - Indeedなう（予選A）

解法②：BFS。最小手数が24手以内であることを利用して枝刈をする。
現在の盤面について、0の数以外の「現在の盤面の位置と最終盤面の位置のマンハッタン距離」の合計をdifとする。difは1手ごとに多くとも1小さくなるため、24手までの残りの手でもdifが0にならないような盤面をその時点で排除するような枝刈を行う。