AT_abc337_d [ABC337D] Cheating Gomoku Narabe

有一个 $H$ 行 $W$ 列的网格。自上而下的第 $i$ 行，自左而右的第 $j$ 列的格子称为格子 $(i, j)$。 每个格子上写有 `o`、`x` 或 `.` 中的某一个字符。每个格子上的字符由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 表示，格子 $(i, j)$ 上的字符与字符串 $S_i$ 的第 $j$ 个字符相同。 对于这个网格，你可以重复进行如下操作任意次（包括 $0$ 次）： - 选择一个写有 `.` 的格子，将其字符改为 `o`。 请判断是否有可能通过若干次上述操作，使得存在纵向或横向连续的 $K$ 个格子，这些格子上的字符全为 `o`（即，满足以下两个条件中**至少一个**）： - 存在整数对 $(i, j)$，满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W-K+1$，使得格子 $(i, j), (i, j+1), \ldots, (i, j+K-1)$ 上的字符全为 `o`。 - 存在整数对 $(i, j)$，满足 $1 \leq i \leq H-K+1$ 且 $1 \leq j \leq W$，使得格子 $(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$。 ## 样例解释 1 进行 $2$ 次操作，例如将格子 $(2, 1)$ 和格子 $(2, 2)$ 上的字符分别改为 `o`，即可满足题目中的条件，这也是最小的操作次数。 ## 样例解释 2 即使一次操作也不进行，也能满足题目中的条件。 ## 样例解释 3 无法满足题目中的条件，因此输出 `-1`。 由 ChatGPT 4.1 翻译