该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个农场中，草地被划分为 $n$ 行 $m$ 列的区域，每个区域可以是草地、障碍物或者喷水器。

农场的布局用一个矩阵表示，其中：

• H 代表喷水器;
• . 代表草地；
• # 代表障碍物。

如何定义一个草地是“湿润的”，如果从一个喷水器出发，最多经过 $D$ 步（上下左右方向）能够到达该地方。喷水器所在的地方也视为湿润。

请计算并输出农场中所有湿润的草地区域的数量。

输入格式

第一行三个整数 $n,m,D$。

接下来 $n$ 行，每行 $m$ 个字符，描述矩阵。

$1\le n,m\le1000$

$1\le D\le n\times m$

输出格式

输出一个整数，表示答案。

3 4 1
H...
#..H
.#.#

5

提示

$(1,1),(1,2),(1,4),(2,3),(2,4)$ 是湿润的草地。