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 翻译