假设你在校园里,每天都要去上课。正如你所看到的,当你匆匆赶到教室时,你惊讶地发现那里的许多座位已经被占用了。今天你和你的朋友去上课,发现有些座位被占用了。
教室有 $$$n$$$ 排座位,每排有 $$$m$$$ 个座位。那么教室可以表示为 $$$n \times m$$$ 矩阵。字符“.”代表空座位,“*”代表座位已被占用。您需要在同一行或同一列中找到 $$$k$$$ 连续的空座位,并为您和您的朋友安排这些座位。你的任务是找出排列座位的方法的数量。如果学生占据的位置不同,则两种方式被认为是不同的。
输入
第一行包含三个正整数$$$n,m,k$$$ ($$$1 \leq n, m, k \leq 2\,000$$$),其中$$$n,m$$$ 代表教室的大小,$$$k$$$ 是你需要找到的连续座位的数量。
接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符“.”或者 '*'。它们形成一个代表教室的矩阵,“.”表示空座位,“*”表示已占用座位。
输出
单个数字,表示在同一行或同一列中查找 $$$k$$$ 空座位的方法数。
示例
输入 #1
2 3 2 **. ...
输出 #1
3
输入 #2
1 2 2 ..
输出 #2
1
输入 #3
3 3 4 .*. *.* .*.
输出 #3
0
注意
在第一个示例中,可以通过三种方式来安排这些座位。您可以选择以下座位进行安排。
- $$$(1,3)$$$, $$$(2,3)$$$
- $$$(2,2)$$$, $$$(2,3)$$$
- $$$(2,1)$$$, $$$(2,2)$$$