题目描述

八数码问题也称为九宫问题。在 $3×3$ 的棋盘，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

输入格式

输入占三行，将 $3×3$ 的初始网格描绘出来；

输出格式

输出占一行，包含一个整数，表示最少交换次数；

本题目标状态一定为

1 2 3

4 5 6

7 8 x

输入样例：

4 7 3
5 x 1
2 6 8

输出样例：

24