AT_abc018_3 [ABC018C] 菱型カウント

有一个纵向 $R$ 行、横向 $C$ 列的矩形区域。从上往下第 $i$ 行（$1 \leq i \leq R$）、从左往右第 $j$ 列（$1 \leq j \leq C$）的格子称为格子 $(i, j)$。这些格子中有一些被涂成黑色，其他格子被涂成白色。 另外，给定一个整数 $K$。 现在，考虑进行如下操作，将一些格子涂成绿色。该操作只进行一次。 - 对于某一整数对 $x$（$K \leq x \leq R-K+1$）、$y$（$K \leq y \leq C-K+1$），对于所有满足 $|i-x|+|j-y| \leq K-1$ 的格子 $(i, j)$，如果该格子原本是白色，则在本次操作中被涂成绿色。对于所有满足 $|i-x|+|j-y| \geq K$ 的格子，则不会被涂成绿色。 问满足上述条件的绿色涂色方法有多少种。这里的“涂色方法”指的是哪些格子被涂成了哪种颜色的组合，不考虑涂色的顺序。

输入以如下格式从标准输入读入。 > $R$ $C$ $K$ > $s_1$ > $s_2$ > $\vdots$ > $s_R$ - 第 $1$ 行包含三个整数 $R$（$3 \leq R \leq 500$）、$C$（$3 \leq C \leq 500$）、$K$（$2 \leq K \leq 500$），表示矩形区域有 $R$ 行 $C$ 列，$K$ 是题目中给定的整数。 - 接下来的 $R$ 行，每行一个长度为 $C$ 的字符串 $s_i$。字符串 $s_i$ 仅由 `o` 和 `x` 两种字符组成，$s_i$ 的第 $j$ 个字符为 `o` 表示格子 $(i, j)$ 是白色，`x` 表示格子 $(i, j)$ 是黑色。

请输出绿色涂色方法的总数，输出一行，末尾需换行。

## 部分分 本题设有部分分。 - 对于满足 $R \leq 50$ 且 $C \leq 50$ 的数据集 1，答对可获得 $30$ 分。 ## 样例解释 1 有如下 $3$ 种情况（`o` 表示白色格子，`x` 表示黑色格子，`\*` 表示绿色格子）： x\*ooo \*\*\*oxo \*ooooxxoo xo\*ooo \*\*\*xoo \*oooxxoo xoooooo \*xoo\*\*\* oxx\*o 由 ChatGPT 4.1 翻译