Cherry Pickup
You are given an n x n grid representing a field of cherries, where each cell is one of three possible integers:
0means the cell is empty, so you can pass through.1means the cell contains a cherry that you can pick up and pass through.-1means the cell contains a thorn that blocks your way.
Return the maximum number of cherries you can collect by following these rules:
- Start at position
(0, 0)and reach(n - 1, n - 1)by moving right or down through valid path cells, which are cells with value0or1. - After reaching
(n - 1, n - 1), return to(0, 0)by moving left or up through valid path cells. - When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell
0. - If there is no valid path between
(0, 0)and(n - 1, n - 1), then no cherries can be collected.
Example 1
0 1 -1 1 0 -1 1 1 1
Input
grid = [[0,1,-1],[1,0,-1],[1,1,1]]Output
5The player can collect 4 cherries on the trip to (2, 2) and 1 more cherry on the return trip, for a maximum total of 5.
Example 2
1 1 -1 1 -1 1 -1 1 1
Input
grid = [[1,1,-1],[1,-1,1],[-1,1,1]]Output
0There is no valid round trip that allows collecting cherries, so the maximum number collected is 0.
Constraints
- n == grid.length
- n == grid[i].length
- 1 <= n <= 50
- grid[i][j] is -1, 0, or 1.
- grid[0][0] != -1
- grid[n - 1][n - 1] != -1