问题 4744 --上课占位置

4744: 上课占位置★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 122  解决: 53
[提交][状态][命题人:]

题目描述

假设你在一个校园里,每天都要去上课。正如你所看到的,当你匆忙走进教室时,你会惊讶地发现很多座位已经被占用了。今天你和你的朋友们去上课,发现有些座位已经坐满了。

教室里有n排座位,每排有m个座位。然后教室可以表示为一个n × m的矩阵。这个角色.表示空座位,而'*'表示座位已被占用。你需要在同一排或同一列找到连续的k个空座位,并为你和你的朋友安排这些座位。你的任务是找出安排座位的方法的数量。

输入

第一行包含三个正整数n, m, k(1n, m, k2 000),其中n, m代表教室的大小,k是你需要找到的连续座位的数量。

后面的n行每一行包含m个字符.*”。它们组成一个矩阵代表教室.表示空座位,'*'表示已坐满座位。

输出

一个数字,表示在同一行或同一列找到k个空座位的方法的数目。

样例输入
Copy
2 3 2
**.
...
样例输出
Copy
3

提示

样例2输入

1 2 2
..

样例2输出

1

样例3输入

3 3 4
.*.
*.*
.*.

样例3输出

0

注释:

针对样例1,有如下三种方式占座位

  • (1,3), (2,3)
  • (2,2), (2,3)
  • (2,1), (2,2)

来源

[提交][状态]