/ Vijos / 题库 /
学姐吃生鱼片
描述
学姐今晚想吃生鱼片, doc便领着她去吃啦. 但是怎么能这样轻易就让馋嘴的学姐吃到生鱼片呢!

图片

于是doc准备了一个"二维魔方".
所谓 二维魔方, 可以被考虑为平面上 3X3 的方格, 里面不重复得填有 1~9 共9个数字.
每一次可以对某一行或某一列向某一方向做轮换操作, 比如说, 如果第三列原来的数字依次为 3 6 9, 那么针对第三列向上轮换一次后 就变成了: 6 9 3; 再向上轮换一次后 就变成了9 3 6.
现在doc给出了 二维魔方的初始状态, 再给出目标状态. 初始状态是由1~9组成的 3X3 的数字方格, 而目标状态中某个位置被标记为星号, 表示可以是任意数字.
如果学姐能用最少的操作次数得到目标状态, doc就会喂她吃一小块生鱼片呢!

格式
输入格式
第一行一个整数T, 表示总的询问次数.
之后有T次询问, 对于每一次询问, 有6行, 每行3组字符(包括数字1~9和星号)以空格隔开.

输出格式
对于每一次询问, 输出一行.
首先输出询问的标号(参见样例输出), 之后输出最少的操作次数. 如果不可能做到, 输出"No Solution!"(不输出引号).

样例1
样例输入1
2
1 2 3
4 5 6
7 8 9
8 * 9
5 3 7
2 * *
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
7 9 8
Copy
样例输出1
Case #1: 7
Case #2: No Solution!
Copy
限制
对于30%的数据, T <= 3
对于60%的数据, T <= 100
对于100%的数据, T <= 1000

题解:
第二题,因为询问非常多,我们尝试预处理BFS一次,然后直接输出答案.

2
10 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
aaab
aaaa
1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2
aaab
aaaa

浙江 周李轩武 提前签到