问题 M: 查理的巧克力工厂
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：16
解决：6
题目描述
查理在继承巧克力工厂后，对于工厂的生产工序进行了调整
在巧克力工厂，每个坚果都是由小松鼠们精心挑选出来的
查理心疼工厂里的每一只小松鼠，因此立下规定：
在对于 $H \times W$ 的大巧克力进行切割包装的过程中，要求切割得到的每一块小巧克力仅包含小于等于 $K$ 粒的坚果
但巧克力工厂的机器对于每块大巧克力只能进行水平或垂直方向的切割，且每次必须从大巧克力的一侧切割到另一侧
机器每次切割都需要花费一定的金钱
查理想要知道，对于一块已知坚果位置的大巧克力可进行的最少切割数，使得切割后的每块小巧克力均符合要求
在巧克力工厂，每个坚果都是由小松鼠们精心挑选出来的
查理心疼工厂里的每一只小松鼠，因此立下规定：
在对于 $H \times W$ 的大巧克力进行切割包装的过程中，要求切割得到的每一块小巧克力仅包含小于等于 $K$ 粒的坚果
但巧克力工厂的机器对于每块大巧克力只能进行水平或垂直方向的切割，且每次必须从大巧克力的一侧切割到另一侧
机器每次切割都需要花费一定的金钱
查理想要知道，对于一块已知坚果位置的大巧克力可进行的最少切割数，使得切割后的每块小巧克力均符合要求
输入
共 $H+1$ 行输入：
第一行包含 $3$ 个整数，依次为 $H$ 、$W$ 、$K$，以空格间隔，
接下来有 $H$ 行，每行包含一个长度为 $W$的字符串，表示一块 $H \times W$ 的大巧克力
对于第 $i$ 行第 $j$ 列的字符 $S_{i,j}$：
若$S_{i,j}=1$，表示大巧克力的第 $i$ 行第 $j$ 列包含一粒坚果；若$S_{i,j}=0$，表示大巧克力的第 $i$ 行第 $j$ 列不包含坚果
$1 \leq H \leq 10$
$1 \leq W \leq 1000$
$1 \leq K \leq H \times W$
$S_{i,j} \in \{0,1\} $
第一行包含 $3$ 个整数，依次为 $H$ 、$W$ 、$K$，以空格间隔，
接下来有 $H$ 行，每行包含一个长度为 $W$的字符串，表示一块 $H \times W$ 的大巧克力
对于第 $i$ 行第 $j$ 列的字符 $S_{i,j}$：
若$S_{i,j}=1$，表示大巧克力的第 $i$ 行第 $j$ 列包含一粒坚果；若$S_{i,j}=0$，表示大巧克力的第 $i$ 行第 $j$ 列不包含坚果
$1 \leq H \leq 10$
$1 \leq W \leq 1000$
$1 \leq K \leq H \times W$
$S_{i,j} \in \{0,1\} $
输出
一个整数，代表大巧克力的最少切割数。
样例输入 复制
3 5 4
11100
10001
00111
样例输出 复制
2
提示
左图为合法切割方法，右图为非法切割方法
