Bessie 相信最愛牧場有特殊草,是世上最好、能使牛多產奶。
各牛回分配吃草點,形成填滿的直角網格。下左例 $NR$ 行($3 \le NR \le 100$)為6,$NC$ 列($3 \le NC \le 100$)為5,牛標 'C'。
她知產奶量 $P_{rc}$($1 \le P_{rc} \le 100$),下右圖標產量。
列 列
1 2 3 4 5 1 2 3 4 5
+-------------- +--------------
1| C C C C C 1| 5 6 7 4 6
行 2| C C C C C 行 2| 7 7 8 6 5
3| C C C C C 3| 9 9 8 3 5
4| C C C C C 4| 8 8 7 6 4
5| C C C C C 5| 4 5 2 4 5
6| C C C C C 6| 3 4 2 3 4找特殊草,即總產量最大的 $3 \times 3$ 牛網格。
找九項和最大 $3 \times 3$ 網格,報左上角位置,先行後列。上右最大71,第2行第1列。
兩 $3 \times 3$ 網格同和取最小行號;同一行仍並列取最小列號。
輸入格式
- 第1行:兩空格分隔整數 $NR$、$NC$。
- 第 $2..NR+1$ 行:第 $r+1$ 行有 $NC$ 空格分隔整數,表示第 $r$ 行。
輸出格式
- 第1行:整數,$3 \times 3$ 最大和。
- 第2行:兩空格分隔整數,最佳 $3 \times 3$ 左上角行、列。
範例
輸入格式 1
6 5 5 6 7 4 6 7 7 8 6 5 9 9 8 3 5 8 8 7 6 4 4 5 2 4 5 3 4 2 3 4
輸出格式 1
71 2 1
題目作者:Rob Kolstad, 2009