Description
Given an n x n grid, pick up maximum cherries traveling from (0,0) to (n-1,n-1) and back. -1 cells are blocked.
Examples
Input:
grid = [[0,1,-1],[1,0,-1],[1,1,1]]Output:
5Explanation:
Maximum 5 cherries can be collected.
Input:
grid = [[1]]Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
grid = [[1,1,0,0],[0,-1,1,0],[1,0,-1,1],[1,0,1,1]]Output:
7Explanation:
Starting from (0,0) to (3,3), one optimal path collects cherries at several positions. On the equivalent second traversal from (0,0) to (3,3), additional cherries along a different path are collected. The combined maximum is 15 cherries.
Constraints
- •
n == grid.length == grid[i].length - •
1 ≤ n ≤ 50