九宫重排

时间限制: 1 Sec
内存限制: 128 MB
提交: 7
正确率: 15 %

题目描述

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

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

把第二个图的局面记为:123.46758

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

本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。


输入

输入第一行包含九宫的初态,第二行包含九宫的终态。


输出

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


样例输入

12345678.
123.46758

样例输出

3

正确答案提交历史

刷题达人榜

  • WriteBug ( 517 )
  • Aline ( 20 )
  • 管理员 ( 23 )
  • Carmelo ( 14 )
  • HMF ( 23 )
  • daocaorenweiyi ( 13 )
eject