#1251. 「USACO 2016 Open Platinum」Bull in a China Shop

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
bcs.in ≫ bcs.out
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 usaco

显示标签

题目描述

Farmer John 决定给他的家增添一些装饰。在当地的瓷器店里,他发现了一尊精致的玻璃牛雕像,决定购买它,因为它完美地适合放在壁炉上方的壁炉架上。

牛雕像的形状由一个 的字符网格描述(),其中小写字母字符代表雕像的各个部分(表示不同的颜色),而 '.' 字符则不代表雕像部分。

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

不幸的是,就在 FJ 准备购买之前,一头公牛冲进了商店,不仅撞碎了 FJ 的雕像,还撞碎了许多其他货架上的玻璃制品!FJ 的雕像碎成了 3 块,并迅速混入了地上的 块碎片中()。每一块碎片都由一个字符网格描述,就像原来的雕像一样。

请帮助 FJ 确定有多少组 3 块碎片(地上的 块中)可以粘合在一起修复他破碎的雕像。

地上的碎片可能被垂直或水平翻转,或者旋转了 90 度的倍数。因此,给定原始网格以及描述碎片的 个网格,你需要找到可以组合成原始图片的 3 块碎片,允许碎片被平移、翻转或旋转 90 度的倍数。当这 3 块碎片叠加在一起时,它们应该准确地形成原始图片,且原始图片中的每个彩色方块都恰好出现在一块碎片中。

输入格式 bcs.in

第一行包含一个整数 。接下来是 个碎片的描述。第一个描述是原始玻璃牛的描述,接下来的 个描述是破碎的碎片。

每个描述以两个整数 )开始。接下来的 行包含 个小写字母字符,描述每个单元格的颜色。每块碎片在水平/垂直方向上都是连通的,并且至少有一个非空单元格。

输出格式 bcs.out

输出满足条件的三元组 )的数量,使得碎片 可以排列成原始玻璃牛。

样例

输入 #1

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

输出 #1

3

数据范围与提示

三个解决方案使用了碎片

请注意,这个问题每个测试用例的时间限制为 6 秒(Java 和 Python 提交的时间限制为 12 秒)。

备注:原文“输入格式”部分中 的范围是 ,而实际数据与之不符,疑为笔误。