《程序设计基础二》类的设计部分练习题目:1432--1446,运算符重载部分练习题目:1447--1461

Problem 1999. -- 九宫重排

1999: 九宫重排

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 10  Accepted: 2
[Submit][Status][Web Board]

Description

  如下面第一个图的九宫格中(3*3),放着 1~8 的数字卡片,还有一个格子空着(用小数点表示)。与空格子相邻的格子中的卡片可以移动到空格中。第一幅图经过若干次移动,可以形成第二个图所示的局面。


  《自己想象图的样子》


  按从上到下,从左到右的顺序记录数字,空格记为句点。

   我们把第一个图的局面记为:12345678.

   把第二个图的局面记为:123.46758
  本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1

Input

  多组测试数据,每组数据第一行包含九宫的初态,第二行包含九宫的终态。

Output

  输出最少的步数,如果不存在方案,则输出-1

Sample Input

12345678.
123.46758
13524678.
46758123.

Sample Output

3
22

[Submit][Status][Web Board]