UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4577. [Usaco2016 Open]Bull in a China Shop

统计 下载数据

Description

农夫约翰决定他的家里需要更多的装饰。通过参观当地的瓷器商店,他决定购买一个精致的玻璃牛雕像,他知道它
将完全适合放在壁炉上方的壁炉架上。牛雕像的形状由一个N×M的字符网格(就像下图)描述(3≤N,M≤500),
其中小写字母描述了雕像的每个部分(表示不同的颜色),'.'字符则不是。
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............
不幸的是,在FJ正准备购买之前,一头公牛穿过商店,不仅打破了FJ的雕像,而且还打破了货架上的许多其他玻璃
制品! FJ的雕像碎成了3片,很快地散落在总共有K块碎片的地面上(4≤K≤100)。每块碎片由一个字符网格描述
,就像描述原来的雕像那样。请帮助FJ确定多少个3块碎片的集合(落在地板上的K块碎片中的其中3块)可以胶合
在一起修补成他的破碎的雕像。地面上的碎片可能已经水平或垂直翻转,或者旋转成了90度的几倍。因此,给定原
始网格以及描述K块碎片的网格,您需要找到3片碎片可以连接在一起以形成原始图像的集合,允许这些碎片被平移
,翻转或旋转90度的倍数。然后当叠加时,3个碎片应该准确地形成原始图形,原始图形中的每个彩色正方形正好
表示其中一片。

Input

第一行包含单个整数K,接下来有K+1个描述片段,第一个片段描述了原始的玻璃牛,剩下的K个片段描述了K块碎片。
对于每个描述片段,第一行包含两个整数R和C(1≤R,C≤100),接下来R行每行C个小写字母或者是'.'。
每个碎片都将被水平/垂直连接并且具有至少一个非空单元(即至少包含一个小写字母)。

Output

输出三元组i,j,k的数目(i <j <k),使得碎片i,j,k可以被拼接为原始的玻璃牛。

Sample Input

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..

Sample Output

3
//共有三个解决方案,分别使用碎片(1,2,3),(1,3,5),(2,4,5)。

Hint

Source

Platinum 鸣谢g1n0st提供译文