#2393. 分割巧克力

分割巧克力

题目描述

HHWW 列的矩形区域,其中每一块是 0011

有分成纵H方格和纵 H方格和纵 W方格网格的巧克力。

从上起第i i 行,从左起第j j 列的方格(i,j) (i,j) 的巧克力,在si,j s_ {i,j} 0时是普通巧克力,1的时候是白巧克力。

将巧克力分成几块,沿着方格边界的直线从网格的一端切到另一端。

为了确保每一块分割后的白巧克力格不超过K K 格,最少需要进行几次操作。

输入格式

输入以以下形式从标准输入给出:

H H W W K K S1,1S1,2...S1,W S_{1,1}S_{1,2}...S_{1,W} : : SH,1SH,2...SH,W S_{H,1}S_{H,2}...S_{H,W}

输出格式

输出所需操作次数的最小值,以便在分割后的任何块中只包含K 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  H  10 1\ \leq\ H\ \leq\ 10
  • 1  W  1000 1\ \leq\ W\ \leq\ 1000
  • 1  K  H × W 1\ \leq\ K\ \leq\ H\ \times\ W
  • Si,j S_{i,j} 0 还是 1

Sample Explanation 1

例如,如下图所示,在第1行和第 1行和第 2行之间分割,3列和第 3列和第 4列之间分割成2块。请注意不能像右边的两张图那样分割。image

Sample Explanation 2

不需要进行操作。