假设你在一个校园里,每天都要去上课。正如你所看到的,当你匆忙走进教室时,你会惊讶地发现很多座位已经被占用了。今天你和你的朋友们去上课,发现有些座位已经坐满了。
教室里有n排座位,每排有m个座位。然后教室可以表示为一个n × m的矩阵。这个角色’.’表示空座位,而'*'表示座位已被占用。你需要在同一排或同一列找到连续的k个空座位,并为你和你的朋友安排这些座位。你的任务是找出安排座位的方法的数量。
假设你在一个校园里,每天都要去上课。正如你所看到的,当你匆忙走进教室时,你会惊讶地发现很多座位已经被占用了。今天你和你的朋友们去上课,发现有些座位已经坐满了。
教室里有n排座位,每排有m个座位。然后教室可以表示为一个n × m的矩阵。这个角色’.’表示空座位,而'*'表示座位已被占用。你需要在同一排或同一列找到连续的k个空座位,并为你和你的朋友安排这些座位。你的任务是找出安排座位的方法的数量。
第一行包含三个正整数n, m, k(1≤n, m, k≤2 000),其中n, m代表教室的大小,k是你需要找到的连续座位的数量。
后面的n行每一行包含m个字符’.’或“*”。它们组成一个矩阵代表教室’.’表示空座位,'*'表示已坐满座位。
一个数字,表示在同一行或同一列找到k个空座位的方法的数目。
2 3 2 **. ...
3
样例2输入
1 2 2
..
样例2输出
1
样例3输入
3 3 4
.*.
*.*
.*.
样例3输出
0
注释:
针对样例1,有如下三种方式占座位