F問題 - 増殖する鶴の剣

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

問題文

C氏は紀元前\(T\)年に発生した鶴の剣信仰について研究している。

C氏は紀元\(1\)年に鶴の剣信仰が流行した地域を調べ上げ、地図として表すことに成功した。 地図は\(H\)個の長さ\(W\)の文字列\(S_i(1 \leq i \leq H)\)からなり、\(S_i\)の\(j\)文字が#のとき座標\((i,j)\)に鶴の剣信仰が存在することを、.のとき存在しないことを表している。

研究の結果紀元前\(T\)年に宇宙より襲来した鶴の剣がいくつかの場所に信仰を植え付けたことがわかっている。 また鶴の剣信仰は中毒性があり、ある座標に鶴の剣信仰があるとき、\(1\)年後にはその座標に斜めを含めて隣接する座標で鶴の剣信仰が行われることがわかっている。

紀元\(1\)年(すなわち鶴の剣襲来から\(T\)年後)の鶴の剣信仰を表す地図と鶴の剣が襲来した年(紀元前\(T\))年が与えられる。

鶴の剣が信仰を植え付けたと考えられる場所の最大数\(K\)を出力せよ。 また条件を満たすような鶴の剣が信仰を植え付けた場所の組が存在しないのならば-1を出力せよ。

制約

• \(1 \leq H,W \leq 300\)
• \(0 \leq T \leq 300\)

入力

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

H W T
S_1
S_2
...
S_H

出力

標準出力に一行で出力してください。

入出力例

入力例1

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

出力例1

2

• 例えばこのような座標に鶴の剣が襲来したと考えられます。

..#..
..#..
.....
.....
.....

入力例2

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

出力例2

-1

• 鶴の剣が襲来したと考えられる条件を満たす座標の組はありません。

入力例3

5 5 0
.###.
.###.
.###.
.....
.....

出力例3

9

入力例4

7 37 1
.###.###.###.###.###.....###.###.###.
.###.###.###.###.###.....###.###.###.
.###.###.#######.#######.###.#######.
.###.###.#######.#######.###.#######.
.###.###.#######.#######.###.#######.
.###.###.....###.....###.###.....###.
.###.###.....###.....###.###.....###.

出力例4

60