AT_abc472_d [ABC472D] Bomber Mad

$ H $ 行 $ W $ 列のグリッドがあります。各マスは、空マスまたは爆弾マスのどちらかです。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と表します。グリッドの情報は $ H $ 個の長さ $ W $ の文字列 $ S_1, S_2 , \dots ,S_H $ によって与えられ、 $ S_i $ の $ j $ 文字目が `.` のとき $ (i,j) $ は空マス、 $ S_i $ の $ j $ 文字目が `#` のとき $ (i,j) $ は爆弾マスです。 また、空マス $ (i,j) $ について $ i $ 行目にも $ j $ 列目にも爆弾マスが存在しないとき、そのマスを **安全な空マス** と呼びます。 $ 1 $ 回の移動で今いるマスから、上下左右に隣り合う空マスに移動することができます（爆弾マスには移動できません）。以下の条件を満たす空マス $ (i, j) $ の数を求めてください。 - $ (i,j) $ から $ K $ 回以下の移動で **安全な空マス** へ到達できる。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ K $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

条件を満たす空マスの個数を出力せよ。

### Sample Explanation 1 **安全な空マス** は $ (2,2) $ だけです。 $ (2,2) $ へ $ 1 $ 回以下の移動で到達できる空マスは $ (1,2),(2,1),(2,2),(2,3),(3,2) $ の $ 5 $ マスですから、答えは $ 5 $ です。 ### Sample Explanation 2 爆弾マスが存在しないため、 $ 6 $ マスすべてが **安全な空マス** です。したがって、どの空マスも移動回数 $ 0 $ 回で条件を満たします。 ### 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 $ は `.` と `#` からなる長さ $ W $ の文字列 - $ H,W,K $ は整数