Cherry Pickup

Problem

Given an n by n grid where 1 is a cherry, 0 is empty and -1 is a thorn, return the maximum cherries collected on a round trip from (0,0) to (n-1,n-1) and back, counting each cell once.

Simulate two walkers moving simultaneously from the top-left, memoising states by (r1, c1, r2) and adding both cells when the walkers occupy different squares. Return -1 if the trip is impossible.

Hint

Because c2 = r1 + c1 - r2, each state needs only three coordinates.

Test cases

case 1

in: [[[0,1,-1],[1,0,-1],[1,1,1]]]

expected: 5

case 2

in: [[[1,1,-1],[1,-1,1],[-1,1,1]]]

expected: -1

case 3

in: [[[1]]]

expected: 1

case 4

in: [[[1,1],[1,1]]]

expected: 4

Starter codePython

def cherry_pickup(grid):
    # Your code here
    pass

4 test cases · run your code against them in the editor