A beach is mapped as a grid beach of m rows and n columns. Each cell holds a whole number: -1 is a rock that nobody can enter, and any other value is the number of shells lying on that patch of sand.
A beachcomber starts on the top-left cell and walks to the bottom-right cell moving only right or down, one cell at a time. Then she walks back to the top-left cell moving only left or up. The first time she stands on a cell she picks up all its shells; a later visit to the same cell finds nothing.
Return the largest number of shells she can collect on the whole loop. If the start or the end is a rock, or there is no way to reach the bottom-right cell at all, return -1.
Examples
Input: beach = [[0, 2, 0],
[3, -1, 1],
[0, 4, 0]]
Output: 10
Explanation: go out along the top row and down the right edge (2 + 1),
come back along the bottom row and up the left edge (4 + 3).
Input: beach = [[0, -1],
[-1, 5]]
Output: -1
Input: beach = [[7]]
Output: 7
Constraints
1 <= m, n <= 50, every row has lengthn- every cell is
-1or between0and100
Goals
- Turn a there-and-back walk into two walkers moving forward together
- Index states by step number so both walkers are always on the same diagonal
- Count a shared cell only once