1818: [NewOJ Week 6] 质数拼图游戏

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:15 通过:8

题目描述

拼图游戏由一个3×3的棋盘和数字1-9组成。目标是达到以下最终状态:
1 2 3
4 5 6
7 8 9
每次如果相邻两个数字之和为质数,则可以进行交换。
相邻:上下左右四联通
给定一个棋盘初始状态,求到达最终状态的最短步数。

输入格式

第一行为正整数T,表示存在T组测试数据,1≤T≤50。
对于每组测试数据,输入3行,每行3个数字表示棋盘。
输入保证合法,棋盘中的9个数字仅为1-9。

输出格式

对于每组测试数据输出一个整数表示答案。如果无法到达最终状态,输出-1。

输入样例 复制

2
7 3 2
4 1 5
6 8 9
9 8 5
2 4 1
3 7 6

输出样例 复制

6
-1

数据范围与提示

第一组测试数据的6步如下: