J10 例题-5 八数码问题

题目描述

有 $3*3$ 的方格，其中有八个数码。初始状态如下：

2 8 3
1 6 4
7 0 5

其中， $0$ 表示空格，空格的上下左右四个方向的相邻数字，都可以移动到空格中，称为一步。 如： $6$ 向下移变成了下面的新状态：

2 8 3
1 0 4
7 6 5

现在给出目标状态，求最小要多少步，才从初始状态移到目标状态。

输入格式

共六行，每行 $3$ 个数字，如题意描述初始状态和结束状态。

输出格式

一个数字，表示最小步数。

样例输入

2 8 3
1 6 4
7 0 5

1 2 3
8 0 4
7 6 5

样例输出

5

样例分析

如上所述。

数据范围

如上所述。