该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

数字华容道（Sliding Puzzle）是一种经典的益智游戏。

在一个 $3\times 3$ 的棋盘上，摆放着编号为 $1\sim 8$ 的数字方块，以及一个空白位置（用数字 $0$ 表示）。

每次操作时，只能将空白位置上下左右相邻的数字移动到空白处，从而改变整个棋盘的状态。

为了方便表示，棋盘状态会被按从上到下、从左到右的顺序压缩成一个 9 位数字串。空着的位置我们用0表示。如图，我们称这个状态为：123456780。

给出一个初始状态，以及最终的目标状态：

1 2 3
8 0 4
7 6 5

请你计算： 从初始状态移动到目标状态，最少需要多少步。

例如：

283104765

对应棋盘：

2 8 3
1 0 4
7 6 5

输入格式

输入一个长度为 9 的数字串，表示数字华容道的初始状态。

其中：

• 0 表示空白格；
• 保证 0~8 每个数字恰好出现一次。

输出格式

输出一个整数，表示从初始状态移动到目标状态所需的最少移动次数。

保证测试数据均有解。

输入输出样例 #1

输入 #1

283104765

输出 #1

4

说明/提示

样例解释

下面是一种可行方案：

283104765
283140765
283145760
283145706
123804765

共需要 $4$ 步。

可以证明，不存在更少步数的方案。

补充小知识

数字华容道最早出现于 19 世纪，是世界上著名的益智游戏之一。

虽然规则看起来简单，但它实际上涉及：

• 图搜索
• 状态压缩
• 广度优先搜索（BFS）
• 最短路径问题

许多人工智能与搜索算法的经典研究，都会使用数字华容道作为测试模型。