八数码问题，就是在一个含有 和 的 方格中，每次可以将 与其相邻位置的数字交换。使得最后变成： 1 & 2 & 3 \\4 & 5 & 6 \\7 & 8 & x\end{pmatrix}" 你要做的就是，对于给定的八数码初始状态，求出交换次数最少的八数码的解决方案。

输入描述:

输入一个 的矩阵 ，元素仅包含 和 。

输出描述:

输出一行一个整数表示矩阵 恢复为最终矩阵所需要的最小步数。