C - Humidifier 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 250 点

問題文

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

各マスの状態は文字 S_{i,j} で表され、 S_{i,j} が # のときそのマスは机、. のときそのマスは床です。床のマスは 2 つ以上存在することが保証されます。

あなたは床のマスから異なる 2 マスを選び、加湿器を設置します。

加湿器が設置されたとき、あるマス (i,j) は加湿器があるマス (i',j') からのマンハッタン距離が D 以下であるとき、またその時に限り加湿されます。 なお、マス (i,j) からマス (i',j') までのマンハッタン距離は |i-i'|+|j-j'| で表されます。 ここで、加湿器が置かれた床のマスは必ず加湿されていることに注意してください。

加湿される 床のマス の個数として考えられる最大値を求めてください。

制約

  • 1 \leq H \leq 10
  • 1 \leq W \leq 10
  • 2 \leq H \times W
  • 0 \leq D \leq H+W-2
  • H,W,D は整数
  • S_{i,j} は # または . である (1 \leq i \leq H, 1 \leq j \leq W)
  • 床のマスは 2 つ以上存在する

入力

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

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

2 5 1
.###.
.#.##

出力例 1

3

マス (1,1) とマス (1,5) に加湿器を置いた時:

  • マス (1,1) の加湿器によってマス (1,1),(2,1) の 2 マスが加湿されます。
  • マス (1,5) の加湿器によってマス (1,5) の 1 マスが加湿されます。

よって、合計 3 マス加湿されています。また、4 マス以上加湿するような加湿器の置き方は存在しないため、答えは 3 です。

入力例 2

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

出力例 2

15

マス (2,4) とマス (5,3) に加湿器を置いた時、15 個の床のマスが加湿されます。

入力例 3

4 4 2
....
.##.
.##.
....

出力例 3

10

Score : 250 points

Problem Statement

The AtCoder company office can be 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 contains a desk; if S_{i,j} is ., that cell is a floor. It is guaranteed that there are at least two floor cells.

You will choose two distinct floor cells and place a humidifier on each.

After placing the humidifiers, a cell (i,j) is humidified if and only if it is within a Manhattan distance D from at least one of the humidifier cells (i',j'). The Manhattan distance between (i,j) and (i',j') is defined as |i - i'| + |j - j'|. Note that any floor cell on which a humidifier is placed is always humidified.

Find the maximum possible number of humidified floor cells.

Constraints

  • 1 \leq H \leq 10
  • 1 \leq W \leq 10
  • 2 \leq H \times W
  • 0 \leq D \leq H+W-2
  • H,W,D are integers.
  • S_{i,j} is # or .. (1 \leq i \leq H, 1 \leq j \leq W)
  • There are at least two floor cells.

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

2 5 1
.###.
.#.##

Sample Output 1

3

When placing humidifiers on (1,1) and (1,5):

  • From the humidifier on (1,1), two cells (1,1) and (2,1) are humidified.
  • From the humidifier on (1,5), one cell (1,5) is humidified.

In total, three cells are humidified. No configuration can humidify four or more floor cells, so the answer is 3.

Sample Input 2

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

Sample Output 2

15

When placing humidifiers on (2,4) and (5,3), 15 floor cells are humidified.

Sample Input 3

4 4 2
....
.##.
.##.
....

Sample Output 3

10