AT_abc472_d.Bomber Mad

有一个 $H$ 行 $W$ 列的网格。每个格子要么是空格子，要么是炸弹格子。记 $(i,j)$ 为从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。该网格由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2 , \dots ,S_H$ 给出：若 $S_i$ 的第 $j$ 个字符为 .，则 $(i,j)$ 是空格子；若为 #，则 $(i,j)$ 是炸弹格子。

对于一个空格子 $(i,j)$，若其所在的第 $i$ 行和第 $j$ 列中均不存在炸弹格子，则称该格子为安全空格子。

每次移动，你可以从当前格子向其上方、下方、左方或右方的相邻空格子移动（不能移向炸弹格子）。请找出满足以下条件的空格子 $(i, j)$ 的数量：

• 从 $(i,j)$ 出发，至多经过 $K$ 次移动即可到达某个安全空格子。

输入从标准输入中按以下格式给出：

$H$ $W$ $K$
$S_1$
$S_2$
$\vdots$
$S_H$

输出满足条件的空单元格数量。

样例 1 解释：
唯一的安全空单元格是 $(2,2)$。从五个空单元格 $(1,2),(2,1),(2,2),(2,3),(3,2)$ 出发，至多经过一步移动即可到达 $(2,2)$，因此答案为 $5$。

样例 2 解释：
由于不存在炸弹单元格，全部六个单元格均为安全空单元格。因此，每个空单元格均满足条件（所需移动步数为零）。

约束条件

• $1 \le H,W \le 5\times 10^5$
• $H\times W \le 5\times 10^5$
• $0 \le K \le H\times W-1$
• $S_i$ 是一个长度为 $W$ 的字符串，仅由字符 . 和 # 组成。
• $H$、$W$ 和 $K$ 均为整数。