Problem B: 五数码谜题

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:63 Solved:30

Description

         在 2×3 棋盘上,放置数码为 1-5 的5个棋牌,剩下一个空格(数字零表示),只能通过棋牌向空格的移动来改变棋盘的布局,最终当目标状态为 { {1,2,3},{4,5,0} } 时谜题被解开。根据给定的谜题初始状态,返回最少可以通过多少次移动达到目标壮态,如果不能解开谜题,则返回 -1 。


 示例1

 输入:puzzle[][]={ 1,0,2,
                                 4,5,3 };  输出: 2


  解释: 如图示,先交换0与2, 再交换0与3, 2步完成 。
     
   示例2
    输入:puzzle[][]={ 1,2,3,
                                    5,4,0 };
    输出:-1    ( 无法完成谜题 )

Input

          输入共二行,谜题两维数组 puzzle[2][3] 。数字间空格分隔。

Output

        输出一个数字,解开谜题的最少移动次数。如果不能解开谜题,则返回 -1

Sample Input Copy

1 0 2
4 5 3

Sample Output Copy

2

HINT

提示:

  • puzzle 是一个 2 x 3 的数组.
  • puzzle 是一个 [0, 1, 2, 3, 4, 5] 的排列。