TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

89.3% (25/28)

Submission's AC Ratio

41.3% (31/75)

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

3 3
1 2 1
2 3 2
1 2 1

Sample Output

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

For Testdata: 0 ~ 4, Score: 13
For Testdata: 5 ~ 9, Score: 38
For Testdata: 10 ~ 14, Score: 49
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 500 65536 65536
1 500 65536 65536
2 500 65536 65536
3 500 65536 65536
4 500 65536 65536
5 500 65536 65536
6 500 65536 65536
7 500 65536 65536
8 500 65536 65536
9 500 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536