Indeedなう予選A D.パズル

問題

H*Wのスライドパズルの状態が与えられる。
左上から
1,2,3,4,5
6,7,8,9,10
...
のように数字を埋めて、右下が0のようにするために必要な最小スライド数を答える。

2<=H,W<=6
最小スライド回数は24回以下が保障される

考え方

両側bfs。

24回以下なので、ゴール状態から12回で行ける状態までを求めておいて、スタート状態から12回で行ける状態までをbfsで求めれば、最小手順が求められる。
3^12=531,441程度で、配列の比較などを含めても十分間に合う。