C - Humidifier 3 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 350

問題文

AtCoder社のオフィスは HW 列のマス目で表されます。上から i 行目、左から j 列目のマスを (i, j) と表します。

各マスの状態は文字 S_{i,j} で表され、 S_{i,j}# のときそのマスは壁、. のときそのマスは床、H のときそのマスは加湿器が置かれた床です。

あるマスは、ある加湿器から壁を通らず上下左右に D 回以下の移動で辿り着ける場合加湿されます。ここで、加湿器が置かれた床のマスは必ず加湿されていることに注意してください。

加湿されている床のマスの個数を求めてください。

制約

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • 0 \leq D \leq H\times W
  • S_{i,j}# または . または H である (1 \leq i \leq H, 1 \leq j \leq W)
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}

出力

答えを出力せよ。


入力例 1

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

出力例 1

5

マス (1,1),(1,2),(1,4),(2,3),(2,4)5 つのマスが加湿されています。


入力例 2

5 6 2
##...H
H.....
..H.#.
.HH...
.###..

出力例 2

21

入力例 3

1 6 3
...#..

出力例 3

0

加湿されるマスが存在しない場合もあります。

Score : 350 points

Problem Statement

The AtCoder company office is represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell has a wall; if S_{i,j} is ., that cell is a floor; if S_{i,j} is H, that cell has a humidifier placed on a floor cell.

A certain cell is considered humidified if it can be reached from at least one humidifier cell by at most D moves up, down, left, or right without passing through a wall. Note that any cell with a humidifier is always humidified.

Find the number of humidified floor cells.

Constraints

  • 1 \leq H \leq 1000
  • 1 \leq W \leq 1000
  • 0 \leq D \leq H\times W
  • S_{i,j} is #, ., or H. (1 \leq i \leq H, 1 \leq j \leq W)
  • All input numbers are integers.

Input

The input is given from Standard Input in the following format:

H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}

Output

Print the answer.


Sample Input 1

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

Sample Output 1

5

Five cells (1,1), (1,2), (1,4), (2,3), (2,4) are humidified.


Sample Input 2

5 6 2
##...H
H.....
..H.#.
.HH...
.###..

Sample Output 2

21

Sample Input 3

1 6 3
...#..

Sample Output 3

0

It is possible that no cells are humidified.