题目描述
在 $3 imes 3$ 的棋盘中放有数字 $1$ 到 $8$ 和一个空格，空格用数字 $0$ 表示。每一步可以将空格与上下左右相邻的一个数字交换。
给定初始局面，请计算变成目标局面 123456780 的最少步数。若无法到达，输出 $-1$。
输入格式
输入一行，一个长度为 $9$ 的字符串，表示初始局面。
输出格式
输出一个整数，表示最少步数；若无法到达，输出 $-1$。
数据范围
输入字符串恰好由数字 $0$ 到 $8$ 各一次组成。
来源说明
本题为 CodeCamp 专项训练题，训练方向参考：洛谷 P1379《八数码难题》。