SP1878 FCATTLE - Farmers Cattle

农夫约翰拥有一头他非常钟爱的奶牛。然而，这头奶牛不幸得了重病，命在旦夕。为了让奶牛活下去，它每天都需要一种特定的药物。假设第 $i$ 天奶牛需要 **medicine**\[i\]。如果 **medicine**\[i\] 为 -1，则表示当天没有合适的药物可用，奶牛将无法存活。 为了挽救奶牛，约翰决定购买一些具有药用价值的牧场。他观察到一片二维网格的牧场，每个格子里都有一种药草。现在，他需要购买一个子矩形区域的牧场，其面积不能超过 **A** (**A** > 1)。通过这片区域的药草，约翰希望尽量长时间地喂养奶牛。 ### 输入格式 输入包括多个测试用例。每个测试用例的第一行包含三个整数 **R**、**C** 和 **A**。第二行是一个以 -1 结束的整数序列，描述每天所需的 **medicine**\[i\]。接下来 **R** 行中，每行含有 **C** 个整数，表示该单元格中的药草类型（1 ≤ **R**, **C** ≤ 200）。所有药草的类型都是非负整数。输入数据最后以一行 "0 0 0" 结束，这行不需要进行处理。 ### 输出格式 对于每个测试用例，输出一行包含 5 个整数： _**days r1 c1 r2 c2**_ （1 ≤ r1 ≤ r2 ≤ R, 1 ≤ c1 ≤ c2 ≤ C） - **_days_** 表示奶牛存活的天数，目标是让这个值最大化。 - 若有多种解决方案，首先选择 r1 最小的。 - 如果仍有多种方案，再选择 c1 最小的。 - 如果仍有多种方案，接着选择 r2 最小的。 - 如果仍然有多种方案，最后选择 c2 最小的。 ### 样例输入 ``` 3 4 6 12 30 12 100 22 -1 30 12 5 3 12 30 100 5 22 3 22 100 3 4 6 2 30 12 100 22 -1 30 12 5 3 12 30 100 5 22 3 22 100 3 4 6 12 30 12 100 22 -1 30 12 5 3 12 30 100 5 22 12 22 100 0 0 0 ``` ### 样例输出 ``` 4 1 1 2 3 0 1 1 1 1 5 1 2 3 3 ``` **本翻译由 AI 自动生成**

无

无