# 741. Cherry Pickup

#### Hard

***

You are given an `n x n` `grid` representing a field of cherries, each cell is one of three possible integers.

* `0` means the cell is empty, so you can pass through,
* `1` means the cell contains a cherry that you can pick up and pass through, or
* `-1` means the cell contains a thorn that blocks your way.

Return *the maximum number of cherries you can collect by following the rules below*:

* Starting at the position `(0, 0)` and reaching `(n - 1, n - 1)` by moving right or down through valid path cells (cells with value `0` or `1`).
* After reaching `(n - 1, n - 1)`, returning 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:**

![](https://assets.leetcode.com/uploads/2020/12/14/grid.jpg)

```
Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.
```

**Example 2:**

```
Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 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`

```python
class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        visited = {}
        return max(self.dfs(0,0,0,0, len(grid), len(grid[0]), grid, visited), 0)
    
    def dfs(self, row1, col1, row2, col2, rows, cols, grid, visited):
        if (row1,col1,row2,col2) in visited:
            return visited[(row1,col1,row2,col2)]
        if row1 == rows or row2 == rows or col1 == cols or col2 == cols or grid[row1][col1] == -1 or grid[row2][col2] == -1:
            return -float("inf")
        if row1 == (rows-1) and row2 == (rows-1) and col1 == (cols-1) and col2 == (cols-1):
            return grid[rows-1][cols-1]
        dfs1 = self.dfs(row1+1, col1, row2+1, col2, rows, cols, grid, visited)
        dfs2 = self.dfs(row1+1, col1, row2, col2+1, rows, cols, grid, visited)
        dfs3 = self.dfs(row1, col1+1, row2+1, col2, rows, cols, grid, visited)
        dfs4 = self.dfs(row1, col1+1, row2, col2+1, rows, cols, grid, visited)
        result = max(dfs1, dfs2, dfs3, dfs4)
        if row1 == row2 and col1 == col2:
            result += grid[row1][col1]
        else:
            result += grid[row1][col1] + grid[row2][col2]
        visited[(row1,col1,row2,col2)] = result
        return result
        
```