题目描述

POJ 1077

一个$\red{3×3}$的方阵由八个数码构成，其中的一个单元是空的，它的周边单元中的数码可以移到该单元中。试找到一个移动序列使初始的无序数码转变为指定的目标状态。如图所示：

输入格式

三行，每行三个整数，表示方阵的开始状态。

输出格式

一个整数，表示最少步数。若在$\red{5 000}$步内无解，则输出“-1”。

样例

输入样例

1 2 3

8 4 0

7 6 5

输出样例

1