问题 4576 --2.拼图游戏(puzzle.cpp)

4576: 2.拼图游戏(puzzle.cpp)

题目描述

  九宫格拼图大家都很熟悉,在 3x3 的格子上摆放 8 块拼图,空出一个格子,玩家要借助这 1个空格上下左右滑动拼图,最终完成整幅图画。 
本题中对拼图进行简化,将正确位置的拼图从左到右自上而下标记为 1-8,空格定义为0,像下面这样: 
1 3 0 
4 2 5 
7 8 6 
每次操作可以将 1块拼图移向空格,像下面这样将 8 块拼图全部归位时完成游戏。 
1 2 3 
4 5 6 
7 8 0 
现在给定拼图的初始状态,希望求出完成拼图最少需要多少次移动。 

输入

输入文件第一行有一个数字 N,表示测试样例组数; 
以下 3*N 行共包含 N 组测试数据,每组测试数据占 3 行,每行 3 个整数,相邻数据用空格隔开。 

输出

输出文件包括 N行,对于每组测试数据,输出最少移动次数。

样例输入输出

输入#1 复制
1 
1 3 0
4 2 5
7 8 6
输出#1 复制
4

提示

【样例说明】 
 
【数据规模与约定】 
1 ≤ N ≤ 30,保证给定的拼图有解。 

序号 标题 作者 发表时间 费用 订购数 操作