AT_abc159_e [ABC159E] Dividing Chocolate

题目描述

有一块被划分为高 $H$ 行、宽 $W$ 列的网格状巧克力。

对于第 $i$ 行第 $j$ 列的格子 $(i, j)$，如果 $S_{i,j}$ 为 0，则该格子是普通巧克力；如果为 1，则是白巧克力。

你可以多次沿着格子的边界，从网格的一端到另一端画直线，将整块巧克力分割成若干块。

请你求出，最少需要进行多少次这样的分割操作，才能使得分割后的每一块中，包含的白巧克力格子的数量都不超过 $K$。

输入格式

输入通过标准输入给出，格式如下：

$H$ $W$ $K$
$S_{1,1}S_{1,2}\ldots S_{1,W}$
$S_{2,1}S_{2,2}\ldots S_{2,W}$
$\vdots$
$S_{H,1}S_{H,2}\ldots S_{H,W}$

输出格式

输出一个整数，表示为了满足每一块中白巧克力格子的数量都不超过 $K$，所需的最小分割操作次数。

输入输出样例 #1

输入 #1

3 5 4
11100
10001
00111

输出 #1

2

输入输出样例 #2

输入 #2

3 5 8
11100
10001
00111

输出 #2

0

输入输出样例 #3

输入 #3

4 10 4
1110010010
1000101110
0011101001
1101000111

输出 #3

3

说明/提示

限制条件

• $1 \leq H \leq 10$
• $1 \leq W \leq 1000$
• $1 \leq K \leq H \times W$
• $S_{i,j}$ 仅为 0 或 1

样例解释 1

例如，可以如左图所示，在第 $1$ 行与第 $2$ 行之间，以及第 $3$ 列与第 $4$ 列之间各切一刀，共 $2$ 次分割即可。
注意，右侧两种分割方式是不允许的。

样例解释 2

无需进行任何分割操作。

由 ChatGPT 4.1 翻译