menu ZJOJ
account_circle 请登录
home
首页
book
题目
apps
分类
play_circle_outline
状态
assessment
竞赛
assignment
作业
equalizer
排名
assignment_ind
登录
person_add
注册
1372: 武器测试
时间限制:2.000s
内存限制:128MB

题目描述

小明参加新武器的测试。为了测试,小明创建了一个多边形。多边形是一个n × m的矩形场,大小为 1 × 1的单位正方形。多边形包含k个对象,每个对象都是矩形并且其边与多边形的边平行,且完全占据个单位正方形。这些物体不相交,也不相互接触。

为了保密,小明只知道可以使用它来击打面积不等于零的任何矩形区域,其边与多边形的边平行。该区域必须完全覆盖多边形被分割成的部分单位正方形,并且不得接触其他正方形。当然,该区域不得跨越多边形边界。

您的任务如下:您应该击中不少于一个且不超过三个矩形对象。每个物体必须完全放置在该区域内(在这种情况下,它被认为是被击中的),或者完全位于该区域之外。



输入格式

第一行有三个整数n, m ,k 1 ≤ n m ≤ 1000 1 ≤ k ≤ 90分别是多边形的大小和物体的数量。接下来的 n行分别包含m个符号并描述多边形。符号"*"代表占据物体的正方形,而符号"."代表空白。符号"*"正好形成k个矩形连接区域,满足任务的要求。

输出格式

输出单个数字表示击中目标的不同方式的数量。

样例输入 content_copy

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

样例输出 content_copy

21

分类