Our airplane can be represented as a square grid of size N × N. Each cell of the grid contains a seat, occupied by a person with some specific uselessness (represented by an integer between -1000 and +1000). A snake enters the airplane at some position. As the snake moves through the grid, he eats each person whose seat it reaches.
The snake has three move commands:
- D
- Move down one or more cells.
- L
- Move left one or more cells.
- R
- Move right one or more cells.
The snake may begin with any of these commands, and must use them in the order LD RD LD RD LD RD…. It may stop at any time.
Here are some examples of correct snake paths (start position is #):
- .#>>v.
....v.
<<<<<.
v.....
v.....
...... - ..#>v.
.v<<<.
.>>>>v
.....v
.<<<<<
...... - ......
..#...
..v...
..>>v.
....v.
...<<. - ......
......
......
..#...
......
......
Since he's had enough of these motherfucking snakes on this motherfucking plane, Samuel L. Jackson wants to find a suitable path for the snake, such that the total uselessness of the people who are eaten is maximum.
Input
The first line of input contains integer N.
Each of the following N lines contains a sequence of N integers each.
Output
The output should contain a single value: the maximum total uselessness that the snake can eat.
Constraints
- N ≤ 1000
- -1000 ≤ matrix values ≤ 1000
- The snake always eats the value on the starting position.
Example
| Input | Output |
|---|---|
| 5 1 1 1 1 1 -1 -1 -1 -1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 1 | 15 |
First, let's take a look at the limits: N ≤ 1000. This suggests the complexity O(N^2). The problem can be solved by DP and the solution should be pretty straight forward.
To make a good solution we'll solve a simpler problem at first. Let's assume D means just one step down. This particular problem can be solved by the folowing DP:
dp[dir][i][j] = the largest sum of a sequence that ends in position (i, j), considering that the snake is coming from direction dir (0 for left or 1 for right).
Returning to the initial problem, the DP seems simpler now: dp[dir][des][i][j] = the largest sum of a sequence that ends in position (i, j), considering that the snake is coming from direction dir (0 for left, 1 for right) and is descending or not (des = 0/1).
The following cases must be analyzed:
- The snake goes down.
- The snake continues to move to the left or to the right.
- The snake stops descending and swaps the direction.
Time complexity: O(N^2).
