问题6814--还原公牛

6814: 还原公牛

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MiB

题目描述

【题目描述】

农夫约翰决定一下他的家。在参观当地的瓷器店时,他发现了一个精致的玻璃牛雕像,他决定买下它,因为他知道它非常适合放在壁炉上方的壁炉架上。

牛雕像的形状由N×N字符网格描述,如下图所示(3≤N≤8),其中“#”字符是雕像的一部分,.’字符不是

...............

...............

...............

#..#...........

####...........

############...

.##.#########..

....#######.##.

....##...##....

....##...##....

...............

...............

...............

...............

...............

 

不幸的是,就在FJ买东西之前,一头公牛跑过商店,不仅打碎了FJ的雕像,还打碎了货架上的许多其他玻璃物品!FJ的小雕像碎成2块,迅速消失在躺在地上的K块小雕像中(3≤K≤10)K件作品中的每一件都由N×N字符网格描述,就像最初的雕像一样。

请帮助FJ确定K块中的哪两块是他需要粘回去修补他的破雕像的。幸运的是,当他的两个小雕像掉到地上时,它们没有旋转或翻转,所以为了重新组装它们,FJ只需要将它们水平或垂直移动,然后叠加。如果他有正确的两件作品,他应该能够以一种完全重建原始雕像的方式来做这件事,原始雕像中的每个“#”都代表在这两件作品中的一件(也就是说,这两件作品,当移动和叠加时,不应该有任何共同的“#”字符,它们一起应该完全形成原始形状)

FJ可以垂直或水平移动任意数量的字符,但它不能移动到任何“#”字符超出原始的N×N网格。每一块的形状不一定由单一的连接区域的“#”字符组成;尽管如此,如果一个片段由多个不相交的“#”字符组成,如果整个片段要移动,那么它们必须全部移动相同的数量。

输入格式】(bcs.in):

第一行输入包含Nk,接下来的N行提供描述FJ原始雕像的字符网格。接下来的KN给出了K个字符网格,指定了FJ在地面上找到的K块字符。

输出格式】(bcs.out):

请打印一行包含两个以空格分隔的整数,每个整数的范围为1…K,指定FJ的两件雕像的索引。解决方案总是存在的,而且是唯一的。你打印的两个数字必须按顺序排列。

样例输入】:

4 3

####

#..#

#.##

....

.#..

.#..

##..

....

####

##..

#..#

####

....

.###

.#..

.#..

样例输出】:

1 3

来源/分类