题目描述

八数码，也叫作“九宫格”，来自一个古老的游戏。

在这个游戏中，你将得到一个$3×$$3$的棋盘和$8$个方块。方块的编号为$1～8$，其中一块方块丢失，称之为“X”。“X”可与相邻的方块交换位置。用符号“r”表示将“X”与其右侧的方块进行交换，用“l”表示左侧的方块，用“u”表示其上方的方块，用“d”表示其下方的方块。

棋盘的状态可以用字符串$S$表示，使用下面显示的规则。

问题是使用“r”“u”“l”“d”操作列表可以将棋盘的状态从状态$A$转到状态$B$，需要找到满足以下约束的结果：

（1）在所有可能的解决方案中，它的长度最小；

（2）它是所有最小长度解中词典序最小的一个。

输入格式

第$1$行是$T （T ≤200）$，表示测试用例数。

每个测试用例的输入都由两行组成，状态$A$位于第$1$行，状态$B$位于第$2$行。

保证从状态$A$到状态$B$都有有效的解决方案。

输出格式

对于每个测试用例，都输出两行。

第$1$行是“Case x :d”格式，其中$x$是从$1$开始计算的案例号，$d$是将$A$转换到$B$的操作列表的最小长度。

第$2$行是满足约束条件的操作列表。

样例

3
24183756X
37216X548
X37814526
237X81645
87416523X
38612754X

Case 1: 23
lluruldrdlurruldrdllurr
Case 2: 19
rddlurdrululddrrull
Case 3: 18
uulddlurdruullddrr

说明

出于学习的目的，我们将第一、二个数据点设置为：$T≤5$。

普通BFS复杂度分析：共有 $9!=326880$ 种情况，可以做到 $log=20$ 判重，有 $T$ 组数据

整体复杂度为： $9!*20 * T=6e6*T$，也就是说普通BFS只能接受 $T≤10$ 的数量级。

来源

HDU3567

2010 ACM-ICPC Multi-University Training Contest（13）——Host by UESTC