#Pold1043. 历届试题 九宫重排

    ID: 379 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>蓝桥杯-历届试题赛制:ACM来源:蓝桥杯练习系统 ID: 42 原题链接: http://lx.lanqiao.cn/problem.page?gpid=T42广搜最短路

历届试题 九宫重排

历届试题 九宫重排

题目描述

如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。 ![](file://RequireFile.do?fid=qYebaGed)![](file://RequireFile.do?fid=HQ3JFM72)   我们把第一个图的局面记为:12345678.   把第二个图的局面记为:123.46758   显然是按从上到下,从左到右的顺序记录数字,空格记为句点。   本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。

输入格式

输入描述:   输入第一行包含九宫的初态,第二行包含九宫的终态。 输入样例: 12345678. 123.46758

输出格式

输出描述:   输出最少的步数,如果不存在方案,则输出-1。 输出样例: 3

数据范围

(原站未提供,导入后需人工补齐)

样例

参考上文 
参考上文

提示

HINT:时间限制:1.0s 内存限制:256.0MB