Bull in a China Shop

题目描述

农夫约翰决定他的家需要更多装饰。来到当地的瓷器店后，他发现了一个精致的玻璃奶牛摆件并决定购买，因为它正好可以摆在壁炉上方的壁炉架上。 奶牛摆件的形状由一个 $N \times M$ 的字符网格描述，如下所示（$3 \leq N, M \leq 500$）。其中小写字母字符表示摆件的一部分（不同字母表示不同颜色），而字符 '.' 表示不属于摆件。 ............... ............... x..x........... xxxx........... xxxxaaaaaaa... .xx.aaaaaaaaa.. ....aaaaaaa.aa. ....ll...ll.... ....vv...vv.... ............... 不幸的是，就在 FJ 准备购买之前，一头公牛冲进商店，把不仅 FJ 的摆件，还有货架上许多其他玻璃制品都打碎了！FJ 的摆件碎成了 3 块，这 3 块很快就混在地上总共 $K$ 块碎片之中（$4 \leq K \leq 100$）。这 $K$ 块中的每一块碎片也都用一个字符网格描述，和原摆件的描述方式一样。 请帮助 FJ 判断：在地上的 $K$ 块碎片中，有多少个由 3 块碎片组成的集合，能够被粘回去修复成他原来的摆件。 地上的碎片可能被上下翻转或左右翻转，或旋转若干个 90 度倍数。因此，给定原始网格以及描述碎片的 $K$ 个网格，你需要找出可以拼成原图的 3 块碎片集合，允许将碎片进行平移、翻转或旋转 90 度的倍数。当把 3 块碎片叠加在一起时，它们应当恰好形成原始图片：原图中的每一个有颜色的格子，必须且只能出现在其中一块碎片中。

输入格式

第一行包含一个整数 $K$。接下来有 $K+1$ 个图形描述。第一个描述的是原始玻璃奶牛，之后的 $K$ 个描述是碎片。 每个描述以一行两个整数 $R$ 和 $C$ 开始（$1 \le R, C \le 100$）。接下来的 $R$ 行每行包含 $C$ 个小写字母字符，描述每个格子的颜色。每块碎片在水平/垂直方向上是连通的，并且至少包含一个非空格子。

输出格式

输出满足 $i < j < k$ 的三元组 $i, j, k$ 的数量，使得第 $i$、$j$、$k$ 块碎片可以被摆放成原始玻璃奶牛。

5
5 5
aaaaa
..a..
bbabb
..a..
aaaaa
3 5
..abb
..a..
aaaaa
5 2
a.
a.
aa
a.
a.
1 2
bb
1 5
bbabb
2 5
aaaaa
..a..

3

提示

三个解分别使用了碎片 $(0, 1, 2)$、$(0, 2, 4)$、$(1, 3, 4)$。 注意：本题每个测试点的时限为 6 秒（Java 和 Python 提交为其两倍）。 题目来源：Brian Dean

标签: USACO|2016|Platinum

来源

USACO|2016|Platinum