题解

题面描述

果园里有一个 $n \times n$ 的网格，每个网格中的数字表示该位置的果树可以采摘的水果数量：

1. 0 表示没有果树可以采摘。
2. -1 表示果树未成熟，不能通过该位置。
3. 其他正整数表示可以采摘的水果数量。

题目内容

果园里有各种果树，周末小明去果园里摘水果，果树的排列是一个 $n*n$ 的网格，每个网格中的数据表示果树可以采摘的水果数量。

为了保证采摘果树有序不被破坏，采摘果树只能从 $(0,0)$ 的位置出发，往某些特定的方向行走，直到走到 $(n-1,n-1)$ 位置再回头，出发时只能向下或者向右行走，回头时只能向上或向左行走回到原始位置 $(0,0)$，由于某些果树未成熟，通过路障进行保护，不让通过，每颗果树只能采摘一次，即去的路上采摘回来路上可以经过但不可以采摘。采摘水果只能进行一次来回。

网格中的数字有如下含义:

1、$0$ 表示没有果树可以采摘;

2、$-1$ 表示果树未成熟不能通过;

3、其他数值表示可以采摘的水果数量。

请你帮忙统计，小明在果园里最多可以采摘的水果数量。

输入描述

输入第一行是 $n$ 的大小，接下来输入 $n$ 行，表示 $n*n$ 的网格数量， $n$ 的取值范围为 $1$ ~ $100$ 。

注意每个网格来回经过只能算采摘一次。

输出描述

输出最多可以采摘的水果数量。

样例1

输入

3
0 2 0
1 -1 0
3 0 1

输出

7

说明

路径 $1$ ：从 $(0,0)$ 出发，向下、向下、向右、向右走到 $(2,2)$ ，这一行程中采摘 $5$ 个水果，然后向上、向上、向左、向左，返回起点，再采摘 $2$ 个水果，共采摘 $7$ 个水果。

如下图中红色的箭头是出发的线路，蓝色的箭头是回来的路线:

路径 $2$ ：从 $(0,0)$ 出发，向右、向右、向下、向下走到 $(2,2)$，这一行程中采摘 $3$ 个水果，然后向左、向左、向上、向上，返回起点，再采摘 $4$ 个水果，共采摘 $7$ 个水果。

两种路径均可

样例2

输入

4
2 0 1 -1
0 -1 3 1
2 0 1 0
4 -1 1 3

输出

14

说明

路径 $1$ ：从 $(0,0)$ 出发，向右、向右、向下、向右、向下、向下走到 $(3,3)$ ，这行程中采摘 $10$ 个水果，然后向左、向上、向左、向左、向上、向上，返回起点，再采摘 $4$ 个水果，共采摘 $14$ 个水果。

提示

在指定的行走规则下输出最多的可以采集的水果数量，只有一次来回。