← 返回题目列表

Codeforces · 39/K

K. 测试

中文机器翻译题面 查看原题

你参加了新武器的测试。为了进行测试,创建了一个多边形。多边形是一个大小为 n × m 的矩形区域,分为大小为 1 × 1 的单位正方形。该多边形包含k个对象,每个对象都是一个有边的矩形,与多边形边平行,并且完全占据几个单位正方形。对象不相交,也不相互接触。

该武器的工作原理是高度机密。你只知道可以用它来敲击任何面积不等于0且边长与多边形各边平行的矩形区域。该区域必须完全覆盖多边形所划分的一些单位正方形,并且不能接触其他正方形。当然,该区域不能跨越多边形边界。你的任务如下:你应该击中不少于1个且不多于3个的矩形物体。每个物体必须要么完全位于该区域内(在这种情况下,它被视为被击中),要么完全位于该区域外。

求击球方式的数量。

输入

第一行有三个整数 n, m и k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 90) — 分别是多边形的大小和其上对象的数量。接下来的 n 行每行包含 m 个符号并描述多边形。符号“*”代表一个方块占据了一个物体,而符号“.”代表一个方块占据了一个物体。代表一个空的空间。符号“*”恰好构成了满足任务要求的k个矩形连通区域。

输出

输出一个数字——击中目标的不同方式的数量。

示例

输入 #1

3 3 3
*.*
...
*..

输出 #1

21

输入 #2

4 5 4
.*.**
...**
**...
...**

输出 #2

38

输入 #3

2 2 1
.*
..

输出 #3

4