← 返回题目列表

AtCoder · abc337_d

G. 作弊奈良部五子

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。

每个单元格包含一个字符 o, x,和 .。每个单元格中写入的字符表示为 H 字符串 S_1, S_2, \ldots, S_H 长度 W;单元格中写入的字符 (i, j) 是 j- 字符串的第一个字符 S_i.

对于此网格,您可以重复以下操作任意次数,可能为零:

  • 选择一个包含字符的单元格 . 并将该单元格中的字符更改为 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 是整数。
  • 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,和 ..

输入

输入由标准输入按以下格式给出:

H W K
S_1
S_2
\vdots
S_H

输出

如果不可能满足问题陈述中的条件,则打印 -1。否则,打印执行此操作所需的最少操作数。


样本输入 1

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

示例输出 1

2

通过操作两次,例如更改单元格中的字符 (2, 1) 和 (2, 2) to o,可以满足问题陈述中的条件,这是所需的最少操作数。


示例输入 2

4 2 3
.o
.o
.o
.o

示例输出 2

0

无需执行任何操作即可满足条件。


示例输入 3

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

示例输出 3

-1

不可能满足条件,所以打印 -1.


示例输入 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