题目描述

有一个 $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 \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$ 均为整数。

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

5

唯一的安全空格是 $(2,2)$。从 $(1,2),(2,1),(2,2),(2,3),(3,2)$ 这五个空格出发，都可以在至多一次移动内到达 $(2,2)$，因此答案为 $5$。

2 3 0
...
...

6

由于不存在炸弹格，全部六个格子都是安全空格。因此每个空格都在移动零次的情况下满足条件。

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

29

• 来源：AtCoder ABC 472 D

子任务设置

• 子任务 1（$30\%$）：$H\times W \le 2000$。
• 子任务 2（$70\%$）：无特殊限制。