Bull in a China Shop

题目描述

Farmer John 决定给家里增添更多装饰。走进当地的瓷器店，他发现了一个精致的玻璃奶牛摆件并决定购买，因为它正好可以放在壁炉上方的壁炉架上。 奶牛摆件的形状由一个 $N \times N$ 的字符网格描述，如下例所示（$3 \leq N \leq 8$），其中字符 '#' 表示摆件的一部分，字符 '.' 表示不是。 ............... ............... ............... #..#........... ####........... ############... .##.#########.. ....#######.##. ....##...##.... ....##...##.... ............... ............... ............... ............... ............... 不幸的是，就在 FJ 购买之前，一头公牛冲进店里，不仅打碎了 FJ 的摆件，还打碎了货架上许多其他玻璃制品！FJ 的摆件碎成了 2 块，并很快混在地上总共 $K$ 块碎片之中（$3 \leq K \leq 10$）。这 $K$ 块碎片中的每一块都用一个 $N \times N$ 的字符网格描述，与原摆件相同。 请帮助 FJ 确定这 $K$ 块碎片中哪两块是他需要粘回去以修复摆件的那两块。幸运的是，当摆件的两块碎片落地时并没有发生旋转或翻转，因此要重新组装它们，FJ 只需要可能在水平方向和/或竖直方向平移碎片，然后将它们叠加。如果他选对了两块碎片，他应该能够通过这种方式精确重建原摆件：原摆件中的每个 '#' 都恰好由两块碎片中的某一块提供（也就是说，两块碎片在平移并叠加后不应有任何重合的 '#' 字符，并且它们合在一起应当恰好形成原来的形状）。 FJ 可以将一块碎片在竖直方向和/或水平方向平移任意多个字符，但不能平移得太远，以至于碎片中的任何 '#' 字符落到原始 $N \times N$ 网格之外。每块碎片的形状不一定由单个“连通”的 '#' 区域构成；尽管如此，如果一块碎片由多个彼此分离的 '#' 团块组成，那么在平移整块碎片时，它们都必须以相同的位移量一起平移。

输入格式

第一行输入包含 $N$ 和 $K$。接下来的 $N$ 行给出描述 FJ 原始摆件的字符网格。接下来的 $KN$ 行给出 $K$ 个字符网格，描述 FJ 在地上找到的 $K$ 块碎片。

输出格式

请输出一行，包含两个用空格分隔的整数，均在范围 $1 \ldots K$ 内，表示属于 FJ 摆件的两块碎片的编号。 保证解一定存在且唯一。你输出的两个数字必须按升序排列。

4 3
####
#..#
#.##
....
.#..
.#..
##..
....
####
##..
#..#
####
....
.###
.#..
.#..

1 3

提示

题目致谢：Brian Dean

标签: USACO|2016|Bronze

来源

USACO|2016|Bronze