AT_abc472_d [ABC472D] Bomber Mad

There is a grid with $ H $ rows and $ W $ columns. Each cell is an empty cell or a bomb cell. Let $ (i,j) $ denote the cell at the $ i $ -th row from the top and the $ j $ -th column from the left. The grid is given by $ H $ length- $ W $ strings $ S_1, S_2 , \dots ,S_H $ : if the $ j $ -th character of $ S_i $ is `.`, $ (i,j) $ is an empty cell, and if the $ j $ -th character of $ S_i $ is `#`, $ (i,j) $ is a bomb cell. For an empty cell $ (i,j) $ , if there is no bomb cell in the $ i $ -th row nor in the $ j $ -th column, that cell is called a **safe empty cell**. In one move, you can move from the current cell to an adjacent empty cell in the up, down, left, or right direction (you cannot move to a bomb cell). Find the number of empty cells $ (i, j) $ satisfying the following condition: - A **safe empty cell** can be reached from $ (i,j) $ in at most $ K $ moves.

The input is given from Standard Input in the following format: > $ H $ $ W $ $ K $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

Output the number of empty cells satisfying the condition.

### Sample Explanation 1 The only **safe empty cell** is $ (2,2) $ . There are five empty cells from which you can reach $ (2,2) $ in at most one move: $ (1,2),(2,1),(2,2),(2,3),(3,2) $ , so the answer is $ 5 $ . ### Sample Explanation 2 Since there is no bomb cell, all six cells are **safe empty cells**. Therefore, every empty cell satisfies the condition with zero moves. ### Constraints - $ 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 $ is a string of length $ W $ consisting of `.` and `#`. - $ H $ , $ W $ , and $ K $ are integers.