- 迷宫密码
【问题描述】猪无戒将蓝兔关在了一座迷宫里。虹猫来到紧闭的迷宫大门前,发现需要输入密码才能将大门打开。守门人告诉他密码就隐藏在门旁的一个方形木盘中。方形木盘中有 m 行 n 列格子,每个格子中刻有一个整数,虹猫需要选择一个数字之和最大的长方形区域来开启迷宫大门。虹猫应该怎么做呢?
注意:应当尽可能避免子矩阵求和的重复运算。
【输入形式】第一行是两个行列数的两个整数 m, n, 0 < m, n <= 100。第二行起是矩阵的元素输入,每个元素在[-32766, 32766]范围内。
【输出形式】两个坐标和一个整数,都用空格隔开。两个坐标分别是是最大长方形左上角和右下角的坐标,从1开始计数。如果有多个相同和的最大长方形,输出左上角坐标行数最小的长方形坐标(同一行有相同和的,输出左上角坐标列数最小的)。整数是最大的和。
【样例输入】
5 4
-1 -2 -3 -4
-3 -2 2 4
-3 -4 3 5
4 -5 3 6
-3 -2 -1 0
【样例输出】
(2, 3) (4, 4) 23