4954. 15 拼图游戏
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 十五数码问题的目标是在$4 \times 4$的单元格上完成拼图，其中一个单元格是空格。 在这个问题中，空格用$0$表示，拼图块用从$1$到$15$的整数表示，如下所示。 ``` 1 2 3 4 6 7 8 0 5 10 11 12 9 13 14 15 ``` 你可以在一步中将一个拼图块移向空格。你的目标是用最少的移动步数使拼图块达到以下配置。 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 ``` 编写一个程序，读取拼图的初始状态，并输出解决该拼图所需的最少步数。 ## 输入格式 给定表示拼图块或空格的$4 \times 4$整数矩阵。 ## 输出格式 在一行中打印最少的步数。 ## 提示 - 给定的拼图最多可在$45$步内解决。 ## 输入 ```in1 1 2 3 4 6 7 8 0 5 10 11 12 9 13 14 15 ``` ## 输出 ```out1 8 ```