Start: Jul, 19, 2023 10:00:00
2023暑CSP-J复赛集训BFS专题
End: Aug, 18, 2024 22:00:00
Time elapsed:
Time remaining:

八数码问题 1221

Time Limit:  1 Sec    Memory Limit:   128 MB
Submission:9     AC:3     Score:100


Description

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

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

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

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

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

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

Input

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

Output

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

Samples

input:
0 4 8 2 6 3 1 7 5 0 2 3 1 8 4 7 6 5
output:
10