OI题库

题4  新版方格取数

【问题描述】

T博士的小儿子小T最近在玩一个游戏。

在一个m行n列的方格中有m*n个数，游戏规则如下：

先在方格边缘取走一个数，以此格为起点，下一步可向该格四个方向中未取数的方格前进，取走该方格的数并继续按如上规则取数。

如果某次取数恰好取到方格的边缘，则下一步可选择离开方格另取入口进入方格，当然也可以选择按上述规则取数。

游戏在小T取完方格内所有数或无法继续取方格内剩下的任何一个数的时候结束。

游戏有这样的得分规则：若方格内的某数j是方格内所有数中第i个取走的数，此次取数的得分为i*j。

小T最后的得分为游戏结束时他各次取数的得分之和。

小T想知道他所能取得的最大得分。

注意：已经取走数的方格不能再次取数或经过。

【输入格式】

输入文件newfgqs.in的第一行是两个正整数m和n，表示方格为m行n列。

第2到m+1行，每行为n个非负整数（注意可能为0），是方格里的数，保证这些数都小于100000（10万）。

【输出格式】

输出文件为newfgqs.out。

只要输出一行，为小T能取得的最大得分。

【样例输入1】

3 3

1 2 3

8 9 4

7 6 5

【样例输出1】

285   （依次取1,2,3,4,5,6,7,8,9）

【样例输入2】

3 3

0 0 0

0 1 0

0 0 0

【样例输出2】

9     （周围绕一圈，第9次取1）

【数据范围】

对于50%的数据，满足m*n<=9。

对于100%的数据，满足m*n<=16。