#1548. SPOJ241 Arranging the Block

内存限制:256 MiB 时间限制:10 Sec

题目描述

输入格式

第一行一个数t(t<=200),表示测试数据的组数。每一组第一行一个数n(n<=200),表示棋盘的大小。接下来n行,每行n个数,第i行第j列一个数a[i,j]表示初始棋盘中的每一个数。再接下来n行,每行n个数,第i行第j列一个数b[i,j]表示目标棋盘中的每一个数。其中a[i,j],b[i,j]<=n*n。

输出格式

对于每组数据,你都要输出一个最小的变换次数,若初始状态不能变换到目标状态则输出”no”。

样例

样例输入


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

样例输出


			
3
2
3
2
3
2
3
2
3
3

数据范围与提示

数据范围:测试点 t n 时限 1 t=10 n=3 1s 2 t=10 n<=10 1s 3 t=50 n<=10 1s 4-5 t=200 n<=100 2s 6-7 t=200 n<=200 7s 8-10 t=200 n=200 15s