← 返回题目列表

Codeforces · 225/C

C. 条形码

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

你有一张 n × m 像素的图片。每个像素可以是白色或黑色。你的任务是改变尽可能少的像素的颜色以获得条形码图片。

如果满足以下条件,图片就是条形码:

- 每列中的所有像素都具有相同的颜色。
- 每条单色垂直线的宽度至少为 x 且最多为 y 像素。换句话说,如果我们将具有相同颜色的像素的所有相邻列分组,则每组的大小不能小于x或大于y。

输入

第一行包含四个空格分隔的整数 n、m、x 和 y(1 ≤ n、m、x、y ≤ 1000;x ≤ y)。

然后跟随 n 行,描述原始图像。每行恰好包含 m 个字符。特点 ”。”代表白色像素,“#”代表黑色像素。图片描述中除了“.”之外没有任何其他字符。和 ”#”。

输出

在第一行中打印要重绘的最小像素数。保证答案存在。

示例

输入 #1

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

输出 #1

11

输入 #2

2 5 1 1
#####
.....

输出 #2

5

注意

在第一个测试样本中,更改一些颜色后的图片可能如下所示:

.##...##...##...##...##...##..

在第二个测试样本中,更改一些颜色后的图片可能如下所示:

.#.#..#.#.