#6575. 八数码问题 普及+/提高

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

三行三列的数组,其元素值为0至8的数。现有如下的变换规则:

1:将0与上面一行元素对换

2:将0与下面一行元素对换

3:将0与左面一行元素对换

4:将0与右面一行元素对换

如果已知一个三行三列元素的初始情况,问最少需几次变换,能变换为指定的一种情况?

输入格式

包括六行的数据,每行有三个以空格分隔的数字。 前三行为原始状态 后三行为目标状态

输出格式

若能在20次以内(包括20)变换得到目标状态的数组,输出最少的变换次数; 若不能在20次以内(包括20)变换得到目标状态的数组,输出No solution!

样例

样例输入

复制0 4 8
2 6 3
1 7 5
0 2 3
1 8 4
7 6 5

样例输出