题目描述

在 $3\times 3$ 的棋盘上摆有 8 张牌，编号 $1\sim8$，另有一个格子为空（用 0 表示）。空格可以与其上、下、左、右相邻的牌交换，记为一步。

给定初始局面，求把它变成目标局面 123804765（按行拼接的 9 个数字）所需的最少步数。若不可达，输出 -1。

目标局面如下：

1 2 3
8 0 4
7 6 5

输入格式

一行 9 个数字（无空格拼接的字符串），表示初始局面，恰好含 0–8 各一次。

输出格式

一个整数，最少步数；不可达输出 -1。

样例输入 #1

283104765

样例输出 #1

4

数据范围

状态总数为 9! 的一半（约 181440 个可达局面）。