#P2578. [ZJOI2005] 九数码游戏

    ID: 1586 远端评测题 1000ms 125MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>2005各省省选浙江Special Judge哈希HASH

[ZJOI2005] 九数码游戏

题目描述

输入格式

输入文件中包含三行三列九个数,同行的相邻两数用空格隔开,表示初始状态每个方格上的数字。初始状态不会是目标状态。

输出格式

如果目标状态无法达到,则输出“UNSOLVABLE”(引号不输出)。

否则,第一行是一个整数S,表示最少的操作次数。接下来4 × (S + 1)行,每四行表示一个状态:前三行每行三个整数,相邻两数用空格隔开,表示每个方格上的数字,第四行是一个空行,作为分隔。第一个状态必须是初始状态,最后一个状态必须是目标状态。

2 3 0
1 8 7
5 4 6

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

提示

由@FlierKing提供SPJ