15 パズルは１つの空白を含む $4 \times 4$ のマス上に 15 枚のパネルが配置され、空白を使ってパネルを上下左右にスライドさせ、絵柄を揃えるパズルです。
この問題では、次のように空白を 0、各パネルを 1 から 15 の番号でパズルを表します。
1 2 3 4 6 7 8 0 5 10 11 12 9 13 14 15
1 回の操作で空白の方向に１つのパネルを移動することができ、ゴールは次のようなパネルの配置とします。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
15 パズルの初期状態が与えられるので、ゴールまでの最短手数を求めるプログラムを作成してください。
入力はパネルの数字あるいは空白を表す $4 \times 4$ 個の整数です。空白で区切られた 4 つの整数が 4 行で与えられます。
最短手数を１行に出力してください。
1 2 3 4 6 7 8 0 5 10 11 12 9 13 14 15
8