← 返回题目列表

AtCoder · past19_o

O. 15 个谜题

中文机器翻译题面 查看原题

分数: 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