AT_abc337_d [ABC337D] Cheating Gomoku Narabe

[problemUrl]: https://atcoder.jp/contests/abc337/tasks/abc337_d $ H $ 行 $ W $ 列のグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,\ j) $ と呼びます。 各マスには `o` 、`x` 、`.` のうちいずれかの文字が書かれています。 各マスに書かれた文字は $ H $ 個の長さ $ W $ の文字列 $ S_1,\ S_2,\ \ldots,\ S_H $ で表され、 マス $ (i,\ j) $ に書かれた文字は、文字列 $ S_i $ の $ j $ 文字目と一致します。 このグリッドに対して、下記の操作を $ 0 $ 回以上好きな回数だけ繰り返します。 - `.` が書かれているマスを $ 1 $ 個選び、そのマスに書かれた文字を `o` に変更する。 その結果、縦方向または横方向に連続した $ K $ 個のマスであってそれらに書かれた文字がすべて `o` であるようなものが存在する（ すなわち、下記の $ 2 $ つの条件のうち**少なくとも一方**を満たす）ようにすることが可能かを判定し、可能な場合はそのために行う操作回数の最小値を出力してください。 - $ 1\ \leq\ i\ \leq\ H $ かつ $ 1\ \leq\ j\ \leq\ W-K+1 $ を満たす整数の組 $ (i,\ j) $ であって、マス $ (i,\ j),\ (i,\ j+1),\ \ldots,\ (i,\ j+K-1) $ に書かれた文字が `o` であるものが存在する。 - $ 1\ \leq\ i\ \leq\ H-K+1 $ かつ $ 1\ \leq\ j\ \leq\ W $ を満たす整数の組 $ (i,\ j) $ であって、マス $ (i,\ j),\ (i+1,\ j),\ \ldots,\ (i+K-1,\ j) $ に書かれた文字が `o` であるものが存在する。

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

問題文中の条件を満たすことが不可能な場合は `-1` を、可能な場合はそのために行う操作回数の最小値を出力せよ。

### 制約 - $ H,\ W,\ K $ は整数 - $ 1\ \leq\ H $ - $ 1\ \leq\ W $ - $ H\ \times\ W\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ K\ \leq\ \max\lbrace\ H,\ W\ \rbrace $ - $ S_i $ は `o` 、`x` 、`.` のみからなる長さ $ W $ の文字列 ### Sample Explanation 1 操作を $ 2 $ 回行って、例えばマス $ (2,\ 1) $ とマス $ (2,\ 2) $ に書かれた文字をそれぞれ `o` に変更することで問題文中の条件を満たすことができ、これが最小の操作回数です。 ### Sample Explanation 2 操作を一度も行わなくても問題文中の条件を満たします。 ### Sample Explanation 3 問題文中の条件を満たすことは不可能なので、`-1` を出力します。