Formatted question description: https://leetcode.ca/all/741.html

741. Cherry Pickup

Level

Hard

Description

In a 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;
  • -1 means the cell contains a thorn that blocks your way.

Your task is to collect maximum number of cherries possible 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: 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.

Note:

  • grid is an N by N 2D array, with 1 <= N <= 50.
  • Each grid[i][j] is an integer in the set {-1, 0, 1}.
  • It is guaranteed that grid[0][0] and grid[N-1][N-1] are not -1.

Solution

This problem is equivalent to finding two paths from position (0, 0) to position (N-1, N-1). If a cell that contains a cherry is in both paths, then the cherry in the cell can only be collected once.

Use dynamic programming. Suppose two paths are simultaneous. At the same time, suppose the cell in the first path is (i, j) and the cell in the second path is (k, m), then there is i + j == k + m, where i, j, k and m are all greater than and equal to 0 and less than N. Therefore, maintain a 3D array dp with size N x N x N, where all the values are -1 initially. Set dp[0][0][0] = grid[0][0]. Then for each tuple (i, j, k), calculate m = i + j - k. If k <= i + j and 0 <= m < N, and both grid[i][j] and grid[k][m] are greater than or equal to 0, consider all four possible cases to reach the current state (either path can be moving right or moving down in the last move), calculate the maximum value of total cherries that can be picked up, and assign the value to dp[i][j][k] if it is not negative.

Finally, obtain the value dp[N - 1][N - 1][N - 1]. If the value is negative, return 0. Otherwise, return the value.

  • class Solution {
        public int cherryPickup(int[][] grid) {
            int length = grid.length;
            int[][][] dp = new int[length][length][length];
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    for (int k = 0; k < length; k++)
                        dp[i][j][k] = -1;
                }
            }
            dp[0][0][0] = grid[0][0];
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    int kMax = Math.min(i + j, length - 1);
                    for (int k = 0; k <= kMax; k++) {
                        int m = i + j - k;
                        if (m < 0 || m >= length)
                            continue;
                        if (grid[i][j] == -1 || grid[k][m] == -1)
                            continue;
                        int num1 = i == 0 || k == 0 ? -1 : dp[i - 1][j][k - 1];
                        int num2 = i == 0 ? -1 : dp[i - 1][j][k];
                        int num3 = j == 0 || k == 0 ? -1 : dp[i][j - 1][k - 1];
                        int num4 = j == 0 ? -1 : dp[i][j - 1][k];
                        int currentCherries = max(num1, num2, num3, num4);
                        if (currentCherries < 0)
                            continue;
                        currentCherries += grid[i][j];
                        if (i != k || j != m)
                            currentCherries += grid[k][m];
                        dp[i][j][k] = currentCherries;
                    }
                }
            }
            return Math.max(0, dp[length - 1][length - 1][length - 1]);
        }
    
        public int max(int num1, int num2, int num3, int num4) {
            return Math.max(Math.max(Math.max(num1, num2), num3), num4);
        }
    }
    
  • // OJ: https://leetcode.com/problems/cherry-pickup/
    // Time: O(N^3)
    // Space: O(N^3)
    // Ref: https://leetcode.com/problems/cherry-pickup/solution/
    class Solution {
    public:
        int cherryPickup(vector<vector<int>>& A) {
            int N = A.size(), memo[51][51][51] = {}; // INT_MIN = non-reachable, -1 = unvisited
            memset(memo, -1, sizeof(memo));
            function<int(int, int, int)> dp = [&](int r1, int c1, int c2) {
                int r2 = r1 + c1 - c2;
                if (r1 == N || r2 == N || c1 == N || c2 == N || A[r1][c1] == -1 || A[r2][c2] == -1) return INT_MIN; // If out-of-bound or non-reachable, return -Infinity
                if (r1 == N - 1 && c1 == N - 1) return A[r1][c1];
                if (memo[r1][c1][c2] != -1) return memo[r1][c1][c2];
                int ans = A[r1][c1];
                if (c1 != c2) ans += A[r2][c2];
                ans += max({ dp(r1, c1 + 1, c2 + 1), dp(r1, c1 + 1, c2), dp(r1 + 1, c1, c2 + 1), dp(r1 + 1, c1, c2) });
                return memo[r1][c1][c2] = ans;
            };
            return max(0, dp(0, 0, 0));
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions