Cherry Pickup

Firdausia Fatima
Last Updated: May 13, 2022

Introduction

One of the most exciting aspects of computer problems is how many various ways they can be solved. Based on several factors, one is superior to the other.

And sorting through all of them to find the finest one is a journey (though not one that will turn you into an alchemist), but one that will teach you a lot.

This is a problem that will completely transform the way you think and widen your range of solutions.

Now that you know how cool this problem is, let’s jump right into it.

 

Problem Statement

You are given an N X N matrix where each cell has either of three states.

0 - This block is free

1 - This block contains a cherry

-1 - This block contains a thorn

Maximize the number of cherries on the round trip from  [0, 0] to [N - 1, N - 1] and then back to [0, 0].

Constraints:

  • You can only take right and down steps while moving from [0, 0] to [N - 1, N - 1].
  • And while coming back from [N - 1, N - 1] to [0,0], you can only take left and up steps.
  • You can pass through the free block.
  • While passing through the cherry block, you can collect the cherry, but after this, it’s a free block.
  • You cannot pass through the block with thorns.

 

If you cannot complete the round trip, return -1.

Example:

Let’s consider this 3 X 3 matrix.

 

As shown in the above image, we can pick a maximum of 3 cherries. Hence, the answer for the above matrix is 3.

Now that we’ve defined the problem. Let’s dive into the solutions.

 

One possible solution is to find the path with the most cherries from top-left to bottom-right and then find the path with the most cherries from bottom-right to top-left.

But, unfortunately for us, this one is incorrect, as you can see in the following example.

If we go from top-left to bottom-right and then back to top-left, taking the maximum cherry count path then,

Path from [0, 0] to [3, 3] = [(0, 0), (0, 1), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3)] 

Path from [3, 3] to [0, 0] = [(3, 3), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0)] 

Cherries Collected = 6 

Now, let’s take the optimal cherry path.

Path from [0, 0] to [3, 3] = [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3)] 

Path from [3, 3] to [0, 0] = [(3, 3), (3, 2), (3, 1), (2, 1), (2, 0), (1, 0), (0, 0)] 

Cherries Collected = 7 

Hence, choosing the maximum Cherry path will not always give maximum cherries in the round trip. 

 

Approach 1

We can solve this problem using Backtracking. Traverse every path from top-left to bottom-right, and for each path, find all paths back to top-right and find the maximum cherry paths. It’s like the cartesian product of all paths down to all paths up.

So we will have two functions( ‘traverseDown’) that will traverse from top-right to bottom-left and one ( ‘traverseUp’ ) that will traverse back from bottom-right to top-left.

 

Program 

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

int maxCherryCount = INT_MIN;

// Function that will try all paths from bottom-right to top-left.
void traverseUp(int r, int c, int n, vector<vector<int>> &arr, int cherryCollected)
{
    // Check if the block is valid.
    if (r < 0 || c < 0 || r >= n || c >= n || arr[r][c] == -1)
    {
        return;
    }

    // If we are back to top-left, that means we have completed the traversal, so we update maxCherryCount.
    if (r == 0 && c == 0)
    {
        maxCherryCount = max(maxCherryCount, cherryCollected);
    }

    // Store cherries in the block.
    int cherries = arr[r][c];

    // Now collect the cherry
    arr[r][c] = 0;

    // Traverse left and up.
    traverseUp(r - 1, c, n, arr, cherryCollected + cherries);
    traverseUp(r, c - 1, n, arr, cherryCollected + cherries);

    // Backtrack.
    arr[r][c] = cherries;
}

// Function to traverse all paths from top-left to bottom-right.
void traverseDown(int r, int c, int n, vector<vector<int>> &arr, int cherryCollected)
{
    // Check if the block is valid.
    if (r < 0 || c < 0 || r >= n || c >= n || arr[r][c] == -1)
    {
        return;
    }

    // Once we have reached the bottom-right now, traverse all paths back to the top-left.
    if (r == n - 1 && c == n - 1)
    {
        traverseUp(r, c, n, arr, cherryCollected);
    }

    // Store cherries in the block.
    int cherries = arr[r][c];

    // Collect cherries.
    arr[r][c] = 0;

    // Traverse right and down.
    traverseDown(r + 1, c, n, arr, cherryCollected + cherries);
    traverseDown(r, c + 1, n, arr, cherryCollected + cherries);

    // Backtrack.
    arr[r][c] = cherries;
}

int main()
{
    int n;
    cout << "Enter the dimension of the matrix (N X N): ";
    cin >> n;
    vector<vector<int>> arr(n, vector<int>(n));
    cout << "Enter the cherry matrix:\n";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
        }
    }

    traverseDown(0, 0, n, arr, 0);

    cout << "Maximum cherries collected: " << maxCherryCount << endl;

    return 0;
}

Input

Enter the dimension of the matrix (N X N): 4
Enter the cherry matrix: 
0 1 0 0 
0 1 0 1
1 1 -1 0
-1 1 1 1

Output

Maximum cherries collected: 8

Time Complexity

O( 2^(4N-4) ), where ‘N’ is the dimension of the matrix.

 

Total steps in a round trip = 4N-4, For moving from [0, 0] to [N - 1, N - 1] we take  2N - 2 steps ( Down steps = N - 1, Right steps = N - 1), so to complete a round trip double the steps of the one-way path. 

For each step, we have two directions to choose from, and hence time complexity is 2 ^ (4N - 4).

Space Complexity

O(4- 4), where ‘N’ is the dimension of the matrix.

Because of the stack space used in recursion, the maximum number of function calls in the stack is 4- 4.

 

Let's see if we can apply Dynamic Programming to the above solution. One requirement for DP is that problems be solved using the solution to smaller subproblems (previously calculated), which is not the case here because we cannot divide the matrix into solved and unsolved sections where the solution to the unsolved part is somehow dependent on previously solved sections. As a result, we'll have to think up a new approach.

 

Approach 2

This time, we'll travel both downward and upward at the same time. So we'll have two robots that go from [0, 0] to [N - 1, N - 1], and when they both reach the bottom right, the MAX_CHERRY_COUNTvariable will be updated. Because one robot travelling in a round trip equals two robots travelling in a downward direction since the second robot’s path can be considered as the backward path for the first robot, let’s look at an example.

 

The number of possible directions both robots can go is - Down Down, Right Right, Right Down, Down Right.

And once we get which direction will give us the maximum number of cherries, we can add them to the current count of cherries and return them.

Let’s try to code it now.

Program 

#include <iostream>
#include <climits>
#include <vector>

using namespace std;

// Function for two robots traversing simultaneously.
int solver(int r1, int c1, int r2, int c2, int n, vector<vector<int>> &arr)
{
    // Check for boundaries. Since we are never decrementing the variables, we omitted the check for r1 < 0.
    if (r1 >= n || c1 >= n || c2 >= n || r2 >= n || arr[r1][c1] == -1 || arr[r2][c2] == -1)
    {
        return INT_MIN;
    }

    // If we've reached the bottom-right block, return its possible value.
    if (r1 == n - 1 && c1 == n - 1)
    {
        return arr[r1][c1];
    }

    int cherries = 0;

    // If robots are on the same block, we've to collect the cherry only once.
    if (r1 == r2 && c1 == c2)
    {
        cherries += arr[r1][c1];
    }
    else
    {
        cherries += arr[r1][c1] + arr[r2][c2];
    }

    // There are four possibility for two robots to move. Either both will move right, or both will move down, or one will move right, and second will move down, or one will move right and second will move down.
    int rr = solver(r1, c1 + 1, r2, c2 + 1, n, arr);
    int rd = solver(r1, c1 + 1, r2 + 1, c2, n, arr);
    int dd = solver(r1 + 1, c1, r2 + 1, c2, n, arr);
    int dr = solver(r1 + 1, c1, r2, c2 + 1, n, arr);

    // Add maximum possible case to the cherries in this block and return.
    cherries += max(max(rr, dd), max(rd, dr));

    return cherries;
}

int main()
{
    int n;
    cout << "Enter the dimension of the matrix (N X N): ";
    cin >> n;
    vector<vector<int>> arr(n, vector<int>(n));
    cout << "Enter the cherry matrix:";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
        }
    }

    int maxxCherryCount = solver(0, 0, 0, 0, n, arr);

    cout << "Maximum Cherries collected : " << maxxCherryCount << endl;

    return 0;
}

Input

Enter the dimension of the matrix (N X N): 4
Enter the cherry matrix: 
0 0 1 0
1 0 1 0
-1 -1 0 1
1 -1 0 1

Output

Maximum Cherries collected: 5

Time Complexity

O(2 ^ (4 * N - 4)), where ‘N’ is the dimension of the matrix.

 

Total steps in each traversal from top-left to bottom-right = 2*(2N - 2) => both robots.

And we have four possibilities (rr, dd, rd, dr).

 

Space Complexity

O(4N-4), where ‘N’ is the dimension of the matrix.

 

Because of stack space used in recursion. The maximum of function calls in the stack is 4- 4.

Approach 2 + DP

Let’s see how and why we can add DP to the above approach.

When we are at the start, robot 1 is at  [r1,c1] and robot 2 is at [r2,c2]. We call four functions one for each case ( Right Right, Down Down, Right Down, Down Right ).

 

And we choose the case whose cherry count is maximum. So if we are in the same situation again, we can use the previously stored result to calculate the answer.

Since there are four variables, we’ll have to make a four-dimensional cache.

All we have to change in the above solution is to cache the result before returning and see if the result is calculated before, then return the result.

Another small improvement is that since both robots are starting from [0,0] and moving one step either right or down, r1+c1 = r2+c2 on every step.

So we can remove c2 from the function call, and it’s not variable now, so the cache dimension is reduced to three.

Program 

#include <iostream>
#include <climits>
#include <vector>
#include <map>

using namespace std;

// Function for two robots traversing simultaneously.
int solver(int r1, int c1, int r2, int n, vector<vector<int>> &arr, map<string, int> &dp)
{
    // Calculate c2.
    int c2 = r1 + c1 - r2;
    // Check for boundaries. Since we are never decrementing the variables, we omitted the check for r1<0.
    if (r1 >= n || c1 >= n || c2 >= n || r2 >= n || arr[r1][c1] == -1 || arr[r2][c2] == -1)
    {
        return INT_MIN;
    }

    // If we've reached the bottom-right block, return its value.
    if (r1 == n - 1 && c1 == n - 1)
    {
        return arr[r1][c1];
    }

    string key = to_string(r1) + " " + to_string(c1) + " " + to_string(r2);

    if (dp.find(key) != dp.end())
    {
        return dp[key];
    }

    int cherries = 0;

    // If robots are on the same block, we've to collect the cherry only once.
    if (r1 == r2 && c1 == c2)
    {
        cherries += arr[r1][c1];
    }
    else
    {
        cherries += arr[r1][c1] + arr[r2][c2];
    }

    // There are four possiblity for 2 robots to move. Either both will move right, or both will move down, or one will move right and second will move down, or one will move right and second will move down.
    int rr = solver(r1, c1 + 1, r2, n, arr, dp);
    int rd = solver(r1, c1 + 1, r2 + 1, n, arr, dp);
    int dd = solver(r1 + 1, c1, r2 + 1, n, arr, dp);
    int dr = solver(r1 + 1, c1, r2, n, arr, dp);

    // Add Maxx possible case to the cherries in this block.
    cherries += max(max(rr, dd), max(rd, dr));

    // Cache the result and return.
    return dp[key] = cherries;
}

int main()
{
    int n;
    cout << "Enter the dimension of the matrix (N X N): ";
    cin >> n;
    vector<vector<int>> arr(n, vector<int>(n));
    cout << "Enter the cherry matrix:\n";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
        }
    }

    unordered_map<string, int> dp;

    int maxxCherryCount = solver(0, 0, 0, n, arr, dp);

    cout << "Maximum cherries collected: " << maxxCherryCount << endl;

    return 0;
}

Input

Enter the dimension of the matrix (N X N): 4
Enter the Cherry matrix: 
0 0 1 0
1 0 1 0
-1 -1 0 1
1 -1 0 0

Output

Maximum Cherries collected: 4

Time Complexity

O( N^3 ), where ‘N’ is the dimension of the matrix.

 

Because we have N ^ 3 dynamic programming states.

Space Complexity

O( N^3 ), where is the dimension of the matrix.

 

Because we have N ^ 3 dynamic programming states, the size required for caching will be O(N ^ 3)

Key Takeaways

Solving questions like these teach you not only computer science concepts but also how to approach complex problems. We’ve got tons of such problems and blogs on the Coding Ninjas Platform. Also, recently Coding Ninjas has released a specially designed test series for acing Interviews- CodeStudio Test Series.

 

Thanks for reading. I hope you’ve gained a lot from this blog.

 

By Firdausia Fatima

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think