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；如果可以，输出所需操作次数的最小值。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

4 2 3
.o
.o
.o
.o

输出 #2

0

输入输出样例 #3

输入 #3

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

输出 #3

-1

输入输出样例 #4

输入 #4

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

输出 #4

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$ 仅由 o、x、. 组成，且长度为 $W$。

样例解释 1

进行 $2$ 次操作，例如将格子 $(2, 1)$ 和格子 $(2, 2)$ 上的字符分别改为 o，即可满足题目中的条件，这也是最小的操作次数。

样例解释 2

即使一次操作也不进行，也能满足题目中的条件。

样例解释 3

无法满足题目中的条件，因此输出 -1。

由 ChatGPT 4.1 翻译