Untitled

public class CherryPickup {

    public static int cherryPickup(int[][] grid) {
        int n = grid.length;
        return Math.max(0, findMaxCherries(grid, 0, 0, 0, 0, n));
    }

    // Recursive function to calculate maximum cherries picked by two players
    private static int findMaxCherries(int[][] grid, int r1, int c1, int r2, int c2, int n) {
        // Base cases: Out of bounds or hitting a thorn
        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
            return Integer.MIN_VALUE;
        }

        // If both players reach the destination
        if (r1 == n - 1 && c1 == n - 1) {
            return grid[r1][c1];
        }

        // Current cell cherries (only count cherries once if both players land on the same cell)
        int cherries = grid[r1][c1];
        if (r1 != r2 || c1 != c2) {
            cherries += grid[r2][c2];
        }

        // Recursive exploration of all possible moves for both players
        int maxCherries = Math.max(
            Math.max(findMaxCherries(grid, r1 + 1, c1, r2 + 1, c2, n), findMaxCherries(grid, r1 + 1, c1, r2, c2 + 1, n)),
            Math.max(findMaxCherries(grid, r1, c1 + 1, r2 + 1, c2, n), findMaxCherries(grid, r1, c1 + 1, r2, c2 + 1, n))
        );

        // Add the current cherries to the result and return
        return cherries + maxCherries;
    }

    public static void main(String[] args) {
        int[][] grid1 = {{0, 1, -1}, {1, 0, -1}, {1, 1, 1}};
        System.out.println(cherryPickup(grid1)); // Output: 5

        int[][] grid2 = {{1, 1, -1}, {1, -1, 1}, {-1, 1, 1}};
        System.out.println(cherryPickup(grid2)); // Output: 0
    }
}