题目详情 - 烤羊排（Hard）

ID: 2717

传统题

1000ms

256MiB

难度: 10

上传者:

题目描述

睿爸今年有多名学生获得NOIP一等奖，徐校长决定宴请这些学生，宴会的主食就是一块长 $H（<21）$ 宽 $W（<1001）$ 的羊排。

徐校长决定亲自下厨，制作烤羊排。

由于徐老师亲自制作的次数太少，羊排烤熟以后，发现有一些地方烤焦了，用 1 表示。

分羊排前，徐老师又想到了一道算法题：

他拿起手中的刀，比划着：

如果从一端到另一端划一刀切割一次羊排。一次切割的两个端点必须平行于羊排的四条边，即不能斜着切割或者阶梯型切割。

问最少需要切割多少次，才能使得分割后的每一块中烤焦的面积不大于 $K$ 。

第一行三个正整数， $H$ 、 $W$ 、 $K$ ，分别表示羊排的长、宽、烤焦面积的限值。

接下来 $H$ 行给出一个字符矩阵，每行 $W$ 个字符，表示羊排的情况， 0 和 1 分别表示熟和焦。

输出一个整数，表示为了满足每一块分割后的羊排烤焦的面积都不超过 $K$ ，所需的最小分割次数。