#J3056. 往返

往返

题目描述

小紫和小蓝在玩一个叫做“往返”的合作游戏。
在游戏开始前,小紫和小蓝划定了游戏场地的大小,即一个边长为n的正方形,同时约定游戏开始时,小紫的坐标是(1, 1),小蓝的坐标是(n, n)。游戏共2轮,第1轮由小紫走,假设现在小紫的坐标是(i, j)。首先,小紫可以往右走,即小紫的坐标变为(i + 1, j);小紫也可以往下走,即坐标变成(i, j + 1)。当小紫到达小蓝所在的坐标即(n, n)时,第一轮结束。接下来开始第2轮,本轮由小蓝走,我们同样假设现在小蓝的坐标是(x, y),首先小蓝可以往左走,即坐标变为(x - 1, y),小蓝也可以往上走,即坐标变为(x, y - 1)。第二轮的结束条件就是小蓝能够成功走到小紫原来所在的坐标,即(1, 1)。需要注意的是,双方只要有一人在移动过程中走出了游戏设置的边界,那么本轮就宣告失败。
在了解了“往返”的游戏规则后,双方又约定了一个获胜条件:因为场地是一个边长为n的正方形,所以我们可以把场地等分成n*n个格子,每个格子上有一个数字,可正可负,小紫和小蓝在移动的时候必须拿走格子上的数字,此时这个格子就变成了一个空格子(可以理解为格子里的数字变成0)。场地外有一个计分板,每当小紫和小蓝取得数字时,计分板上的分数都会增加/减少,只要两轮能够顺利进行下来,且最终分数能够超过比赛开始前约定的数字,那么本次“往返”游戏就是成功的。
显然每局“往返”游戏都存在一个最大可获得的分数,那么假定已知本局游戏的格子数量和每个格子中的数字,请你编写程序找出本局游戏的最大可获得分数。

输入格式

输入共n+1行。
第1行是一个正整数n,表示游戏场地的边长是n。
第2~n+1行,每行有n个整数,表示第i行第j列方格中的数字是aij。

输出格式

输出本局“往返”游戏可获得的最大分数。
2
11 14
16 12
53

提示

样例解释:
对于小紫来说,最优路线是(1, 1) -> (1, 2) -> (2, 2),第一轮分数为11+16+12=39。对于小蓝来说,最优路线是(2, 2) -> (2, 1) -> (1, 1),第二轮分数为0+14+0=14,最终分数为39+14=53。
数据约定:
对于100%的数据:
1 ≤ n ≤ 200
-1000 ≤ aij ≤ 1000