Find maximum strawberries collected


  • 0
    J

    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


  • 0
    A

    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))])

Log in to reply
 

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