Eight

这个15字谜已经存在了100多年，即使你不知道它的名字，你现在也看到了它。 它是用15个滑动瓷砖建造的，每个瓷砖上的数字从1到15不等，所有这些都被包装成一个4×4的框架，一个瓷砖缺失了。让我们将丢失的瓷砖称为“x”；拼图的目标是排列这些瓷砖，以便按如下顺序排列： ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x ``` 唯一合法的操作是将“x”与其共享边缘的瓷砖之一交换。作为一个例子，下面的移动顺序解决了一个稍微混乱的谜题： ``` (见原题那四个图) ``` 前一行中的字母指示'x'瓷砖的哪个相邻的块在每一步与'x'瓷砖交换；值分别为'r'、'l'、'u'和'd'，分别用于右、左、上和下。如'r'，表示将'x'右边的瓷砖移到空白'x'。 并非所有的谜题都能解决；1870年，一个名叫山姆·洛伊德的人因发现无法解决的谜题而出名，并令许多人感到沮丧。 实际上，要将一个常规的谜题变成一个无法解决的难题，所要做的就是交换两个瓷砖(当然，不包括丢失的'x'瓷砖)。 在这个问题中，你将编写一个程序来解决不太知名的8数码问题，由八个瓷砖组成。 移动规则同15个滑动瓷砖一样。 在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要怎么移动（用'x'表示空格） 目标状态： ``` 1 2 3 4 5 6 7 8 x ``` 一个测试点包括多个测试数据， 第一行n表示测试数据个数， 接下来1~n+1行，会给出n个初始状态。 状态描述方法 ``` 原状态： 1 2 3 x 4 6 7 5 8 输入时的描述 1 2 3 x 4 6 7 5 8 ``` 注意输出格式有以下两点需要注意： 1. 请在除最后一组数据以外的输出后面额外打上一行空行 2. 若输入的谜题无需移动就能被解决，请输出一个空行即可

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=593 [PDF](https://uva.onlinejudge.org/external/6/p652.pdf) 



1
2 3 4 1 5 x 7 6 8

ullddrurdllurdruldr