分数: 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