分数: 6 点
问题陈述
A 4\times 4 网格据说是 好 如果处于以下状态:
对于每个整数 i 之间 1 和 15,包含在内,只有一个单元格上写有该整数。
没有其他单元格上写有任何内容。换句话说,只有一个单元格上没有写任何内容。
你有两个不同的好网格 S 和 T.
这里,好格子 S 由下式给出 16 整数 S_{i,j} (1\leq i,j\leq 4).
If 1\leq S_{i,j}\leq 15,这意味着单元格中
上面写着 i从顶部开始的第行和 j从左边算起第 S_{i,j} ;
if S_{i,j}=-1,这意味着单元格中
上面写着 i从顶部开始的第行和 j从左边算起第 1 列没有写任何内容。
同样, T 由下式给出 16 整数 T_{i,j} (1\leq i,j\leq 4).
求执行下列操作使网格等于的最少次数 T,从 S.
如果网格不能等于 T 与 30 次以内(包括任意次数的操作都可以做到的情况),打印 -1 。
- 选择与未写入任何内容的单元格相邻的单元格,并将所选单元格上写入的整数写入空单元格。然后,擦除所选单元格上写入的整数。
约束
- -1\leq S_{i,j},T_{i,j}\leq 15
- S_{i,j},T_{i,j}\neq 0
- S 和 T 是明显的好网格。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
S_{1,1} S_{1,2} S_{1,3} S_{1,4}
S_{2,1} S_{2,2} S_{2,3} S_{2,4}
S_{3,1} S_{3,2} S_{3,3} S_{3,4}
S_{4,1} S_{4,2} S_{4,3} S_{4,4}
T_{1,1} T_{1,2} T_{1,3} T_{1,4}
T_{2,1} T_{2,2} T_{2,3} T_{2,4}
T_{3,1} T_{3,2} T_{3,3} T_{3,4}
T_{4,1} T_{4,2} T_{4,3} T_{4,4}
输出
打印执行问题陈述中的操作以使网格等于的最小次数 T,从 S.
如果网格不能等于 T 与 30 操作或更少,打印 -1 。
示例输入 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 -1 1 2 3 4 5 6 -1 8 9 10 7 11 13 14 15 12
示例输出 1
3
我们表示为 (i,j) 中的单元格 i从顶部开始的第行和 j- 网格中从左侧算起的第列。
In S,空单元格是 (4,4).
可以执行三个操作来获取 T.
- 选择 (3,4)。 写 12 to (4,4),并擦除写入的整数 (3,4).
- 选择 (3,3)。 写 11 to (3,4),并擦除写入的整数 (3,3).
- 选择 (2,3)。 写 7 to (3,3),并擦除写入的整数 (2,3).
另一方面,人们无法获得 T 有两个或更少的操作,所以打印 3.

示例输入 2
-1 11 10 9 1 12 15 8 2 13 14 7 3 4 5 6 6 5 4 3 7 12 15 2 8 13 14 1 9 10 11 -1
示例输出 2
-1
无法获得 T 与 30 操作还是更少,所以打印 -1.
示例输入 3
1 12 11 10 2 13 -1 9 3 14 15 8 4 5 6 7 1 10 5 14 2 11 6 15 3 12 7 -1 4 13 8 9
示例输出 3
30