Cherry Pickup

Problem statement

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:

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

My solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
var cherryPickup = function(grid) {
    let result = 0;
    let N = grid.length;
    let cache = new Map();
    let cherries;
    
    function traverse(x1, y1, x2, y2) {
        if (x1 === N - 1 && y1 === N - 1) {
            return grid[x1][y1] !== -1 ? grid[x1][y1] : Number.MIN_SAFE_INTEGER;
        }
        
        
        if (x1 > N -1 || y1 > N -1 || x2 > N - 1 || y2 > N - 1 || grid[x1][y1] === -1 || grid[x2][y2] === -1) {
            return Number.MIN_SAFE_INTEGER
        }
        
        
        const key = `${x1}:${y1}:${x2}:${y2}`;
        if (cache.has(key)) {
            return cache.get(key)
        }
        
        
        if (x1 === x2 && y1 === y2) {
            cherries = grid[x1][y1];
        } else {
            cherries = grid[x1][y1] + grid[x2][y2];
        }
        
        // console.log(x1, y1, x2, y2, cherries)
        
        result = cherries + Math.max(
            traverse(x1 + 1, y1, x2 + 1, y2),
            traverse(x1, y1 + 1, x2, y2 + 1),
            traverse(x1 + 1, y1, x2, y2 + 1),
            traverse(x1, y1 + 1, x2 + 1, y2)
        );
        
        // console.log("result", key, traverse(x1 + 1, y1, x2 + 1, y2))
        
        
        cache.set(key, result);
        return result;
        
        
    }
    // console.log("Number.MIN_SAFE_NUMBER", Number.MIN_SAFE_INTEGER)
    result = traverse(0, 0, 0, 0)
    
    // console.log(cache)
    return result > 0 ? result : 0;
};