题目描述
【题目描述】
农夫约翰决定装饰一下他的家。在参观当地的瓷器店时,他发现了一个精致的玻璃牛雕像,他决定买下它,因为他知道它非常适合放在壁炉上方的壁炉架上。
牛雕像的形状由N×N字符网格描述,如下图所示(3≤N≤8),其中“#”字符是雕像的一部分,’.’字符不是。
...............
...............
...............
#..#...........
####...........
############...
.##.#########..
....#######.##.
....##...##....
....##...##....
...............
...............
...............
...............
...............
不幸的是,就在FJ买东西之前,一头公牛跑过商店,不仅打碎了FJ的雕像,还打碎了货架上的许多其他玻璃物品!FJ的小雕像碎成2块,迅速消失在躺在地上的K块小雕像中(3≤K≤10)。K件作品中的每一件都由N×N字符网格描述,就像最初的雕像一样。
请帮助FJ确定K块中的哪两块是他需要粘回去修补他的破雕像的。幸运的是,当他的两个小雕像掉到地上时,它们没有旋转或翻转,所以为了重新组装它们,FJ只需要将它们水平或垂直移动,然后叠加。如果他有正确的两件作品,他应该能够以一种完全重建原始雕像的方式来做这件事,原始雕像中的每个“#”都代表在这两件作品中的一件(也就是说,这两件作品,当移动和叠加时,不应该有任何共同的“#”字符,它们一起应该完全形成原始形状)。
FJ可以垂直或水平移动任意数量的字符,但它不能移动到任何“#”字符超出原始的N×N网格。每一块的形状不一定由单一的“连接”区域的“#”字符组成;尽管如此,如果一个片段由多个不相交的“#”字符组成,如果整个片段要移动,那么它们必须全部移动相同的数量。
【输入格式】(bcs.in):
第一行输入包含N和k,接下来的N行提供描述FJ原始雕像的字符网格。接下来的KN行给出了K个字符网格,指定了FJ在地面上找到的K块字符。
【输出格式】(bcs.out):
请打印一行包含两个以空格分隔的整数,每个整数的范围为1…K,指定FJ的两件雕像的索引。解决方案总是存在的,而且是唯一的。你打印的两个数字必须按顺序排列。
【样例输入】:
4 3
####
#..#
#.##
....
.#..
.#..
##..
....
####
##..
#..#
####
....
.###
.#..
.#..
【样例输出】:
1 3