# Find maximum strawberries collected

• There is a garden of strawberry plants represented by a 2D, square array. Each plant
represents an element in the matrix, i.e., it has a number of straberries. If a plant
doesn't have strawberries it is denoted by 0. If 0 is encountered you cannot travel
through that path.

You can start from any cell along the left border of this ground (i.e., the matrix) and
travel until it finally stops at one cell in the right border, and you can only move to
up/down/right. You can only visit each cell once. Calculate the maximum number of berries
is obtained.

Also there are some special conditions:

• Even in the left border and right border, we can go up and down.
• When we are at the top cell of one column, we can still go up, which
demands us to pay all current strawberries, then we will be
teleported to the bottom cell of this column and vice versa.

Input: user enters dimensions of ground i.e. size of matrix and the matrix itself.

Output: the maximum number of strawberries collected without encountering 0

• ## did test

def pick(matrix):
max_v = -0x80000000
for y in range(len(matrix)):
dp = [[0]*len(matrix[0]) for _ in matrix]
r = pick_strawberry(dp, matrix, y, 0, 0)
if r > max_v:
max_v = r
return max_v

def pick_strawberry(dp, matrix, start_y, x, curr):
if x >= len(matrix[0]): return
for target_y in range(len(matrix)):
y = start_y
sum_v = curr
while y != target_y:
if matrix[y][x] == 0:
dp[target_y][x] = 0
else:
sum_v += matrix[y][x]
if y == len(len(matrix)):
sum_v = 0
y = (y+1)%len(len(matrix))
dp[target_y][x] = sum_v + matrix[target_y-1][x]
while y != target_y:
if matrix[y][x] == 0:
dp[target_y][x] = max(dp[target_y][x], 0)
else:
sum_v += matrix[y][x]
if y == -1:
sum_v = 0
y = (y+len(matrix))%len(len(matrix))
dp[target_y][x] = max(dp[target_y][x], sum_v + matrix[target_y+1][x])
for y in range(len(matrix)):
pick_strawberry(matrix, y, x+1, curr)

return max([matrix[y][len(matrix[0]-1)] for y in range(len(matrix))])

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.