#P4577. [Usaco2016 Open]Bull in a China Shop
[Usaco2016 Open]Bull in a China Shop
题目描述
农夫约翰想买一座玻璃牛雕像。小写字母表示雕像格子的颜色,句点表示空格子。下面是一个可能的形状。
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............
一头公牛闯进商店,把雕像摔成了三块,也打碎了其它玻璃制品。地上共有 块碎片,求有多少种取出三块不同碎片来拼回原雕像的方法。
每块选中的碎片都可以独立平移、水平或竖直翻转,或旋转 的整数倍。拼好后,原图中的每个有色格必须恰好由一个同色格覆盖,原图之外与原图中的空格都不能覆盖任何有色格。同一组三块碎片无论有多少种拼法都只计一次。
输入格式
第一行是整数 。接下来有 个网格,第一个是原雕像,之后按顺序给出编号 至 的碎片。
每个网格先给出两个整数 ,接下来 行,每行 个字符。每个字符是小写英文字母或句点。每块碎片至少含一个有色格,其有色格通过上下左右相邻相互连通。
输出格式
输出一行一个整数,表示能拼成原雕像的三元组 的数量,其中 。
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
样例解释
三种碎片组合的编号分别为 、 和 。
数据范围
。原雕像的行、列数都在 至 之间。每块碎片的网格行、列数都在 至 之间。