九数码游戏
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
九数码游戏
题目描述
这是一个很古老的游戏了：有一个3x3的活动拼盘，方格上写有0~8这九个数字。
利用拼盘背后的旋钮，游戏者每次可以进行以下两种操作之一。
- 将拼盘外围的8个方格按顺时针挪一个位置。
- 将中间一行向右移动一个位置，最右边的方格被移到最左边。
操作示例： 初始：
3 7 5
2 6 1
4 8 0
进行操作1后：
2 3 7
4 6 5
8 0 1
进行操作2后：
2 3 7
5 4 6
8 0 1
输入格式
输入文件中包含三行三列九个数，同行的相邻两数用空格隔开，表示初始状态每个方格上的数字。初始状态不会是目标状态。
输出格式
如果目标状态无法达到，则输出“UNSOLVABLE”（引号不输出）。
否则，第一行是一个整数S，表示最少的操作次数。接下来4 × (S + 1)行，每四行表示一个状态：前三行每行三个整数，相邻两数用空格隔开，表示每个方格上的数字，第四行是一个空行，作为分隔。第一个状态必须是初始状态，最后一个状态必须是目标状态。
步数相同的情况下,优先操作1
输入输出样例 #1
输入 #1
2 3 0
1 8 7
5 4 6
输出 #1
4
2 3 0
1 8 7
5 4 6
1 2 3
5 8 0
4 6 7
1 2 3
0 5 8
4 6 7
0 1 2
4 5 3
6 7 8
0 1 2
3 4 5
6 7 8
