1719 測資加強 已 rejudge
1279 . 填方格遊戲－續
TopCoder
Tags
Description
填方格遊戲除了多人模式之外，還有一種不為人所知的單人模式。
有一個$m$乘$n$的方格，每格內有一個非負整數。一開始你的分數是零。每次你都可以選一個還沒被圈過的數，把他圈起來，並且計算出你圈的數字以及與他相鄰（有公共邊）的格子中有圈的那些的總和。算出這個總和之後，將這個總和加到你的分數。繼續這個操作直到整個方格都圈完了。
作為一個單人模式遊戲，你的目標當然是使你自己的分數愈高愈好。然而這個方格有點大，所以你決定藉助程式之力幫你玩這個遊戲。
Input Format
第一行有兩個正整數$m,n\leq 10^ 3$，代表方格的大小。
接下來的$m$行，每行有$n$個小於$10^ 9$的非負整數，代表方格內填的數。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $mn\leq 10$ | 13 |
| 2 (5~9) | $m=1, n\leq 500$ | 38 |
| 3 (10~14) | 無限制 | 49 |
Output Format
請輸出一個數，代表分數的最高可能值。
Sample Input 1
3 3
1 2 1
2 3 2
1 2 1
1 2 1
2 3 2
1 2 1
Sample Output 1
43
Hints
一種達到43分的方法：
先圈3：3分；
再圈左邊的2：5分，總計8分；
再圈上面的2：5分，總計13分；
再圈右邊的2：5分，總計18分；
再圈下面的2：5分，總計23分；
再圈左上角的1：5分，總計28分；
再圈右上角的1：5分，總計33分；
再圈右下角的1：5分，總計38分；
最後圈左下角的1：5分，總計43分。
Problem Source
Problem set / Description by Paupière
建國中學105學年度校內第一次模擬賽pD
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 13 |
| 2 | 5~9 | 38 |
| 3 | 10~14 | 49 |