#546. [语言月赛202303] Carrot Harvest G
[语言月赛202303] Carrot Harvest G
题目描述
有 行 列共 个坑,每个坑可能有一个萝卜,也可能没有。
现在 Farmer John 需要至少拔 个萝卜,他只能挑一个矩形(长方形或正方形)区域的坑进行拔萝卜。
请你求出,为了至少拔 个萝卜,他需要挑的矩形面积(坑的数量)最小是多少。
输入格式
输入共 行。
第一行为三个整数 。
第二行至第 行,每行 个只可能为 或 的整数。其中第 行的第 个整数为 ,代表第 行第 列的坑中是否有萝卜。 代表有萝卜, 代表没有萝卜。
输出格式
输出共一行一个整数,代表为了至少拔 个萝卜,Farmer John 需要挑的矩形的最小面积(坑的数量)。
5 5 7
0 0 0 1 0
0 0 1 1 1
0 1 1 1 1
0 1 1 0 0
0 0 0 0 1
8
提示
样例 1 解释
如下图所示,绿色底色的方格为有萝卜的区域,白色底色的方格为无萝卜的区域。红色框起的区域为一种拔萝卜的区域,使用 的面积拔了 个萝卜。可以证明不存在工作面积更小的拔萝卜方式。
数据规模与约定
对于 的数据,保证 ,。
测试点编号 | |||
---|---|---|---|
数据保证一定有至少一种拔萝卜的方式可以拔至少 个萝卜。