The Cherry Pickup problem involves locating the maximum number of cherries that can be collected by two people starting at opposite ends of a grid and moving toward one another. In this Answer, we’ll evaluate the problem statement and provide a solution in Python.

We’re provided an `n x n`

grid that represents a garden where each cell contains some cherries. We need to find the maximum number of cherries that can be collected while following these rules:

The person starts at

`(0,0)`

and reaches`(n-1,n-1)`

.When a person encounters a cherry in the cell, they pick it up.

No cherries can be collected without a

between the start and end.valid path A valid path is one that is connected from start to finish without encountering any thorns.

Each cell can have one of the following three values:

`0`

**:**The cell is empty, and the person can walk through.`1`

**:**There is a cherry the user can pick up and pass through.`-1`

**:**There is a thorn that blocks the person’s path.

The two rules of traversal are:

Move right or down from the start

`(0, 0)`

to the end`(n-1, n-1)`

Move left or up from the end

`(n-1, n-1)`

to the start`(0, 0)`

.

An example of this garden grid is illustrated below:

This is our starting grid

In the above example, we can pick up 3 cherries with a valid path while avoiding all the thorns in the grid.

Q

Which of the following correctly defines the rules for the Cherry Pickup problem on an `n x n`

grid?

A)

Two people start at opposite ends of the grid and collect cherries along a path. The maximum number of cherries picked determines the solution.

B)

Starting at `(0,0)`

and reaching `(n-1,n-1)`

, a person collects cherries in cells marked `1`

, avoiding thorns marked `-1`

.

C)

The person starts at `(n-1,n-1)`

and moves to `(0,0)`

, collecting cherries and avoiding thorns.

D)

Cherries are collected by one person, starting at any cell, moving in any direction, and summing the cherries encountered.

Imagine we have two robots tasked with picking cherries from the grid. The robots start at the top-left corner and must move to the bottom-right corner, maximizing their cherry collection.

The algorithm maximizes cherry (represented by `1`

) collection while navigating obstacles represented by `-1`

. We will employ a dynamic programming approach.

Initialize a 3D table (

`dictionary`

) to store calculated results.Define a helper function (

`table`

) to:Consider the possible movements of two robots.

Recursively explore their paths.

Handle boundaries or obstacles by returning a large negative value.

Return the cherry count at the bottom-right corner.

Evaluate potential moves for both individuals, counting cherries collected.

Explore four movements

Both right

One down, one right

One right, one down

Both down

Select the maximum cherry count among these moves.

Store the maximum cherry count in the dictionary.

Let's see this algorithm in action.

Let's see this grid, with both robots starting at (0, 0).

The following is the solution to this problem:

def cherryPickup(garden):n = len(garden) # Get the dimensions of the garden (assumed to be square)dictionary = [[[-float('inf')] * n for _ in range(n)] for _ in range(n)] # Initialize a 3D table (dictionary) with -infinity to store cherry counts at each position for both robotsdef table(x1, y1, x2): # Define a recursive helper function (table) to explore pathsy2 = x1 + y1 - x2 # Calculate the y-coordinate of the second robot based on the constraint x1 + y1 = x2 + y2# Base cases: out of bounds, obstacle, or reached the goalif x1 == n or y1 == n or x2 == n or y2 == n or garden[x1][y1] == -1 or garden[x2][y2] == -1:return -1000000 # Return a very low value for invalid paths or paths hitting obstaclesif x1 == y1 == x2 == n - 1: # Reached the bottom-right cornerreturn garden[x1][y1] # Return the cherry count at the final positionif dictionary[x1][y1][x2] != -float('inf'): # If this state has been visited beforereturn dictionary[x1][y1][x2]res = garden[x1][y1] # Cherry count at the current position of the first robotif x1 != x2: # If the robots are not on the same squareres += garden[x2][y2] # Add the cherry count of the second robot's positionnextitem = max(table(x1, y1 + 1, x2 + 1), # Both robots move righttable(x1 + 1, y1, x2 + 1), # First robot down, second robot righttable(x1, y1 + 1, x2), # First robot right, second robot downtable(x1 + 1, y1, x2) # Both robots move down)dictionary[x1][y1][x2] = res + nextitem # Store the result in the dictionaryreturn dictionary[x1][y1][x2] # Return the calculated maximum cherry countresult = max(0, table(0, 0, 0)) # Start the search from the top-left corner, Ensure the result is non-negative (0 if no valid path)return resultgarden = [[0,1,-1],[1,0,-1],[1,1,1]]print(cherryPickup(garden))

The explanation is as follows:

**Line 1:**We define the`cherryPickup`

function, which takes`garden`

(n x n grid of cherries) as a parameter.**Line 2:**The`n`

stores the size of the garden.**Line 3:**This is a 3D list with the initial values. The`-float('inf')`

is applied to the areas not visited yet.**Lines 5:**The helper function`table`

that calculates the maximum number of cherries that can be collected.**Lines 8–9:**We check if it’s encountering a thorn. If it does, it returns a very negative value`-1000000`

.**Lines 12–13:**If the current position is at the bottom-right corner of the garden, it means we’ve reached the end, and the function returns the number of cherries.**Lines 15–16:**If we’ve already computed this and stored in`dictionary`

, we return that cached result.**Line 17:**Otherwise, we calculate the result in the current cell.**Lines 19–20:**We check if positions are equal. If they aren’t, add the number to`res`

.**Lines 22–27:**We calculate`res`

for the next four possible moves.**Line 32:**We return the final result.**Lines 34–35:**This is the code to call the function.

The time complexity of this problem is

The space complexity of this problem is `dictionary`

array, which stores intermediate results for subproblems in

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS