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

    ID: 3680 传统题 2500ms 256MiB 尝试: 7 已通过: 2 难度: 9 上传者: 标签>难度分类提高+/省选-枚举与搜索暴力枚举字符串二维哈希双哈希随机化与近似随机哈希数据结构哈希表排序与序列处理二维前缀和二分查找CF2600Platinum鸣谢g1n0st提供译文

[Usaco2016 Open]Bull in a China Shop

题目描述

农夫约翰想买一座玻璃牛雕像。小写字母表示雕像格子的颜色,句点表示空格子。下面是一个可能的形状。

...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............

一头公牛闯进商店,把雕像摔成了三块,也打碎了其它玻璃制品。地上共有 KK 块碎片,求有多少种取出三块不同碎片来拼回原雕像的方法。

每块选中的碎片都可以独立平移、水平或竖直翻转,或旋转 90∘90^\circ 的整数倍。拼好后,原图中的每个有色格必须恰好由一个同色格覆盖,原图之外与原图中的空格都不能覆盖任何有色格。同一组三块碎片无论有多少种拼法都只计一次。

输入格式

第一行是整数 KK。接下来有 K+1K+1 个网格,第一个是原雕像,之后按顺序给出编号 11 至 KK 的碎片。

每个网格先给出两个整数 R,CR,C,接下来 RR 行,每行 CC 个字符。每个字符是小写英文字母或句点。每块碎片至少含一个有色格,其有色格通过上下左右相邻相互连通。

输出格式

输出一行一个整数,表示能拼成原雕像的三元组 (i,j,k)(i,j,k) 的数量,其中 1≤i<j<k≤K1\le i<j<k\le 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

样例解释

三种碎片组合的编号分别为 (1,2,3)(1,2,3)、(1,3,5)(1,3,5) 和 (2,4,5)(2,4,5)。

数据范围

4≤K≤1004\le K\le 100。原雕像的行、列数都在 33 至 500500 之间。每块碎片的网格行、列数都在 11 至 500500 之间。