582 . 魔法棋盤
TopCoder
Tags
Description
探險家千里在走了上百里的路途後，終於找到了傳說中埋藏寶藏的遺跡，為了走入遺跡，找到寶藏，千里必須破解層層關卡：
每一道關卡都有一枚主教棋以及一張有大小為 $n\times m$ 的魔法棋盤，魔法棋盤上的每個格子都有一個正整數，代表該格子的魔力值，根據石碑上的說明，千里必須將主教放在棋盤上的某個方格，使得主教攻擊範圍內的總魔力值最大化才可以破解關卡，主教的攻擊範圍是對角線上的所有位置，特別注意放置主教的那個格子也算在主教的攻擊範圍內。危險的是，如果千里放錯的話就會被夜光閃亮亮復仇鬼吃掉。
身為一個路過的好心人，你決定告訴千里魔力值總和的最大值作為提示。
以下是主教的攻擊範圍的圖示：
Input Format
第一行包含一個正整數 $t\ (1\le t\le 1000)$ 代表測資的數量。
每一筆測資的第一行包含兩個正整數 $n, m\ (1\le n, m\le 200)$ 代表棋盤的大小。
接下來的 $n$ 行，每一行都包含 $m$ 個數字，分別是方格棋盤由上而下，由左而右的魔力值，魔力值皆為不超過 $10^ 6$ 的非負整數，同一行的數字之間以空白分隔。
此外，所有測資的 $n\times m$ 的總和不會超過 $40000$
Output Format
對於每一筆測資請輸出一個整數，代表該筆測資中，主教攻擊範圍內的魔力值總和的最大值，每筆測資的輸出之間以換行分隔。
Sample Input 1
4
4 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4
2 1
1
0
3 3
1 1 1
1 1 1
1 1 1
3 3
0 1 1
1 0 1
1 1 0
4 4
1 2 2 1
2 4 2 4
2 2 3 1
2 4 2 4
2 1
1
0
3 3
1 1 1
1 1 1
1 1 1
3 3
0 1 1
1 0 1
1 1 0
Sample Output 1
20
1
5
3
1
5
3
Hints
Problem Source
Codeforces 1676D
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~12 | 無額外限制 | 100 |