You are given an $n \times n$ grid representing a field of cherries. Each cell in the grid can have one of three possible values:

• $0$: An empty cell that can be walked through

• $1$: A cell containing a cherry that can be picked and then passed through

• $-1$: A cell containing a thorn, which cannot be crossed

Your task is to find the maximum number of cherries that can be collected while following these rules:

1. Start at the top-left corner $(0,0)$ and reach the bottom-right corner $(n-1,~n-1)$ by only moving right or down through valid cells ($0$ or $1$).

2. After reaching the bottom-right corner, return to the starting point $(0, 0)$ by only moving left or up through valid cells.

3. When passing through a valid cell containing a cherry, pick it up, and the cell becomes empty (its value changes from $1$ to $0$).

4. If there is no valid path between $(0,0)$ and $(n-1,~n-1)$, then no cherries can be collected. Return $0$.

Note: A valid path requires traveling from the top-left corner to the bottom-right corner and successfully returning to the starting point.

Constraints:

• n == grid.length

• n == grid[i].length

• $1 \leq$ n $\leq 30$

• grid[i][j] is $-1$, $0$, or $1$.

• grid[0][0] != $-1$

• grid[n - 1][n - 1] != $-1$

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Implement your solution in the following coding playground.