Cheating Gomoku Narabe

题目描述

有一个 $H$ 行 $W$ 列的网格。记 $(i, j)$ 为从上数第 $i$ 行、从左数第 $j$ 列的格子。 每个格子包含字符 $o$、$x$ 或 $.$ 中的一种。每行的字符由长度为 $W$ 的 $H$ 个字符串 $S_1, S_2, \ldots, S_H$ 表示；格子 $(i, j)$ 中的字符是字符串 $S_i$ 的第 $j$ 个字符。 在这个网格上，你可以任意多次（也可以为零次）重复下面的操作：

选择一个字符为 $.$ 的格子，并将该格子的字符改为 $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$。否则，输出实现该目标所需的最小操作次数。

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

2

4 2 3
.o
.o
.o
.o

0

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

-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 \leq H$ $1 \leq W$ $H \times W \leq 2 \times 10^5$ $1 \leq K \leq \max\lbrace H, W \rbrace$ $S_i$ 是长度为 $W$ 的字符串，且仅由字符 $o$、$x$ 和 $.$ 组成。例如，通过两次操作，将格子 $(2, 1)$ 和 $(2, 2)$ 的字符改为 $o$，可以满足题目中的条件，并且这是所需的最少操作次数。
无需进行任何操作即可满足该条件。
无法满足该条件，因此输出 $-1$。

标签: AtCoder|abc337D

来源

AtCoder|abc337D