作弊的五子棋

题目描述

有一个 $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（即是否满足以下两个条件中的至少一个）。如果可能，输出达到该状态所需的最少操作次数。

• 存在满足 $1 \le i \le H$ 且 $1 \le j \le W-K+1$ 的整数对 $(i,j)$，使得格子 $(i,j), (i,j+1), \ldots, (i,j+K-1)$ 中的字符全部是 o。
• 存在满足 $1 \le i \le H-K+1$ 且 $1 \le j \le 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。否则，输出满足条件所需的最少操作次数。

样例

3 4 3
xo.x
..o.
xx.o

2

例如，执行两次操作，将格子 $(2,1)$ 和 $(2,2)$ 中的字符改成 o，即可满足题目条件，并且这是所需的最少操作次数。

4 2 3
.o
.o
.o
.o

0

不进行任何操作就已经满足条件。

3 3 3
x..
..x
.x.

-1

无法满足条件，因此输出 -1。

10 12 6
......xo.o..
x...x.....o.
x...........
..o...x.....
.....oo.....
o.........x.
ox.oox.xx..x
....o...oox.
..o.....x.x.
...o........

3

数据范围

• $H, W, K$ 是整数。
• $1 \le H$
• $1 \le W$
• $H \times W \le 2 \times 10^5$
• $1 \le K \le \max\{H, W\}$
• $S_i$ 是由 o、x、. 组成的长度为 $W$ 的字符串。