P2578 [ZJOI2005] 九数码游戏
题目描述
这是一个很古老的游戏了：有一个 $3 \times 3$ 的活动拼盘（如下图），方格上写有 $0 \sim 8$ 这九个数字。例如：
$$
\begin{array}{|c|c|c|}
\hline
3 & 7 & 5 \\ \hline
2 & 6 & 1 \\ \hline
4 & 8 & 0 \\ \hline
\end{array}
$$
利用拼盘背后的旋钮，游戏者每次可以进行以下两种操作之一：
1. 将拼盘外围的 $8$ 个方格按顺时针挪一个位置。
2. 将中间一行向右移动一个位置，最右边的方格被移到最左边。
例如：
$$
\begin{array}{|c|c|c|}
\hline
3 & 7 & 5 \\ \hline
2 & 6 & 1 \\ \hline
4 & 8 & 0 \\ \hline
\end{array}
\xrightarrow{\text{进行操作 1}}
\begin{array}{|c|c|c|}
\hline
2 & 3 & 7 \\ \hline
4 & 6 & 5 \\ \hline
8 & 0 & 1 \\ \hline
\end{array}
\xrightarrow{\text{进行操作 2}}
\begin{array}{|c|c|c|}
\hline
2 & 3 & 7 \\ \hline
5 & 4 & 6 \\ \hline
8 & 0 & 1 \\ \hline
\end{array}
$$
给你一个拼盘的初始状态，你能用最少的操作次数把拼盘变成下图所示的目标状态吗？
$$
\begin{array}{|c|c|c|}
\hline
0 & 1 & 2 \\ \hline
3 & 4 & 5 \\ \hline
6 & 7 & 8 \\ \hline
\end{array}
$$
输入格式
输入文件中包含三行三列九个数，同行的相邻两数用空格隔开，表示初始状态每个方格上的数字。初始状态不会是目标状态。
输出格式
如果目标状态无法达到，则输出“UNSOLVABLE”（引号不输出）。
否则，第一行是一个整数 $S$，表示最少的操作次数。接下来 $4 \times (S + 1)$ 行，每四行表示一个状态：前三行每行三个整数，相邻两数用空格隔开，表示每个方格上的数字，第四行是一个空行，作为分隔。第一个状态必须是初始状态，最后一个状态必须是目标状态。
说明/提示
由@FlierKing提供SPJ