問題文
縦 R 行、横 C 我有一个矩形区域的列。从上面 i (1 ≦ i ≦ R) 行,从左起 j (1 ≦ j ≦ C) 选择列中的单元格 ( 我们将其称为i, j)。其中一些方块被漆成黑色,另一些被漆成白色。
另外,一些整数 K 已定义。
现在,考虑绘制新的绿色,以满足以下条件。仅执行此操作一次。
- 一组整数 对于 x (K ≦ x ≦ R - K + 1), y (K ≦ y ≦ C - K + 1) ,| 所有满足i-x|+|j-y|≦ K - 1 (i,j),正方形(i,j) 原本是一个白色的方块,通过此操作被涂成绿色。此外,| 对于每个满足i-x|+|j-y|≧ K 的方块,该方块不会被漆成绿色。
像这样应用颜色的方法共有多少种?不过,这里的涂色方法是指给哪些方格赋予哪种颜色的组合,而不考虑颜色涂色的顺序。
入力
输入将以以下形式从标准输入给出。
R C K s_1 s_2 : s_R
- 1 行中,3 整数 R (3 ≦ R ≦ 500), C (3 ≦ C ≦ 500), K (2 ≦ K ≦ 500) 用空格分隔。这意味着矩形面积是 R 行、横 C 表示有一个列。K 是文本中定义的整数。
- 2 在 R 行提供有关正方形的信息。R 行数过多 i (1 ≦ i ≦ R) 行显示长度 C 字符串
给出 s_i 。字符串 s_i 是
它仅由
o,x的 2 类型的字符组成, 从s_i 左侧开始 j (1 ≦ j ≦ C) 第一个字符是o奈良广场 (i,j) 是一个白色方块,x奈良广场 (i,j) 代表黑色方块。
部分点
针对此问题设置了部分分数。
- R ≦ 50 和 满足 C ≦ 50 的数据集 如果您正确回答 1 , 给出30 点。
出力
绘制绿色的方法总数 在 1 行输出。在输出末尾插入换行符。
入力例1
4 5 2 xoooo oooox ooooo oxxoo
出力例1
3
下面 3 街道可以考虑(o 是一个白色方块,x 是一个黑色方块,* 代表绿色方块)。
| x | * | o | o | o |
| * | * | * | o | x |
| o | * | o | o | o |
| o | x | x | o | o |
| x | o | * | o | o |
| o | * | * | * | x |
| o | o | * | o | o |
| o | x | x | o | o |
| x | o | o | o | o |
| o | o | o | * | x |
| o | o | * | * | * |
| o | x | x | * | o |
入力例2
4 5 2 ooooo oxoox oooox oxxoo
出力例2
0
入力例3
8 6 3 oooooo oooooo oooooo oooooo oxoooo oooooo oooooo oooooo
出力例3
4