600126 - 最短路++
在一个3×3的矩阵上,0-8共9个数字,其中数字0可以和上下左右相邻的数字交换位置,但其他数字之间不可以交换位置;例如01、02之间可以交换位置12、68之间不可以。给出矩阵初始状态,求出矩阵达到目标状态123804765最少需要多少次交换?
注:矩阵状态用一行连续连续数字表示,每3个数字依次表示第一行从左到右、第二行从左到右、第三行从左到右的数字,例如目标状态123804765在矩阵中为:
123
804
765
Input
一行,由0-8这9个数字构成,表示矩阵当前状态。
Output
达到目标状态所需的最少交换次数。
Examples
Input
283104765
Output
4