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

题目描述

在一个 $3\times 3$ 的棋盘上，由上往下，由左往右依次摆放着数字 $0\sim 8$ 共 $9$ 个数字，其中 $0$ 表示为空的位置，其余位置都有一个相对应编号的棋子。现在给你最初的摆放排列方式，我们保证数据存在解，你需要做的是输出变为目标排列的最小步骤。

游戏规则规定，每个棋子每次只能移动一步，且只能向空的位置移动。

输入格式

输入初始状态共一行九个字符。

输出格式

输出一个整数，即变化到目标状态的最小步骤。

样例

283104765

4

提示说明

假设我们最开始的状态是 $283104765$ ,我们想要变为的状态是 $123804765$ 对应的摆放与操作步骤如下。