题目描述

有一个 $H$ 行 $W$ 列的网格。每个格子要么是空格子，要么是炸弹格。用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。

网格由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, 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
...
S_H

输出格式

输出满足条件的空格子个数。

输入示例 1

3 3 1
#..
...
..#

输出示例 1

5

示例 1 说明

第 $1$ 行和第 $1$ 列都有炸弹，第 $3$ 行和第 $3$ 列也都有炸弹，所以唯一的安全空格子是 $(2,2)$。

$1$ 步以内能到达 $(2,2)$ 的空格子有 $(1,2), (2,1), (2,2), (2,3), (3,2)$ 共 $5$ 个，答案为 $5$。注意 $(2,2)$ 自己算 $0$ 步，也要计入。

输入示例 2

2 3 0
...
...

输出示例 2

6

示例 2 说明

没有炸弹格，所以 $6$ 个格子全都是安全空格子。于是每个空格子都能用 $0$ 次移动满足条件。这组数据用来检验 $K = 0$ 的边界：起点自己就是安全格时必须算进答案。

输入示例 3

5 7 2
..#....
..#....
.......
...#...
...#...

输出示例 3

29

示例 3 说明

有炸弹的行是第 $1, 2, 4, 5$ 行，有炸弹的列是第 $3, 4$ 列，因此安全空格子只能落在第 $3$ 行且列号不属于 $\{3,4\}$，即 $(3,1), (3,2), (3,5), (3,6), (3,7)$ 共 $5$ 个。以这 $5$ 个格子为起点做多源扩展，$2$ 步以内可达的空格子共 $29$ 个。

约束条件

• $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$ 均为整数