#2393. 分割巧克力
分割巧克力
题目描述
有 行 列的矩形区域,其中每一块是 或
有分成纵 W方格网格的巧克力。
从上起第行,从左起第列的方格的巧克力,在 0
时是普通巧克力,1
的时候是白巧克力。
将巧克力分成几块,沿着方格边界的直线从网格的一端切到另一端。
为了确保每一块分割后的白巧克力格不超过格,最少需要进行几次操作。
输入格式
输入以以下形式从标准输入给出:
输出格式
输出所需操作次数的最小值,以便在分割后的任何块中只包含的白巧克力格。
样例 #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
数据范围与提示
- 是
0
还是1
Sample Explanation 1
例如,如下图所示,在第 2行之间分割, 4列之间分割成2块。请注意不能像右边的两张图那样分割。
Sample Explanation 2
不需要进行操作。