t.py

class Solution(object):
    def cherryPickup(self, grid):
        previous_locs = {(0, 0, 0, 0) : grid[0][0]}
        n = len(grid)
        for step in range(1, 2 * (n - 1) +1):
            if len(previous_locs) == 0:
                return 0
            curr_locs = dict()
            locs = self.get_all_possible_pos(step, grid, n)
            print locs
            print
            for loc in locs:
                tmp = self.max_previous_steps(loc, previous_locs, n)
                if tmp != None:
                    curr_locs[loc] = locs[loc] + tmp
            previous_locs = curr_locs
        return max([previous_locs[all_path] for all_path in previous_locs])

    def max_previous_steps(self, loc, previous_locs, n):
        prevs = [(-1, 0, -1, 0), (0, -1, 0, -1), (-1, 0, 0, -1), (0, -1, -1, 0)]
        x1, y1, x2, y2 = loc
        max_cherries = 0
        can_reach = False
        for prev in prevs:
            new_x1, new_y1, new_x2, new_y2 = x1 + prev[0], y1 + prev[1], x2 + prev[2], y2 + prev[3]
            if (new_x1, new_y1,new_x2,new_y2) in previous_locs:
                can_reach = True
                possible_cherries = previous_locs[(new_x1, new_y1, new_x2, new_y2)]
                if possible_cherries > max_cherries:
                    max_cherries = possible_cherries
        if can_reach:
            return max_cherries
        return None


    def get_all_possible_pos(self, step, grid, n):
        all_locs_for_one = set()
        all_possible_pos = dict()
        for i in range(step):
            x1, y1 = i, step - i
            if 0 <= x1 < n and 0 <= y1 < n:
                all_locs_for_one.add((x1, y1))
                if x1 == 0 or y1 == 0:
                    all_locs_for_one.add((y1, x1))
        for loc1 in all_locs_for_one:
            for loc2 in all_locs_for_one:
                x1, y1 = loc1
                x2, y2 = loc2
                if grid[x1][y1] != -1 and grid[x2][y2] != -1:
		    if (x1, y1) == (x2, y2):
			all_possible_pos[(x1, y1, x2, y2)] = grid[x1][y1]
		    else:
			all_possible_pos[(x1, y1, x2, y2)] = grid[x1][y1] + grid[x2][y2]
        return all_possible_pos

print Solution().cherryPickup([
[1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-1,1,1],
[1,1,1,1,1,1,1,1,-1,-1,1,1,1,1,1,1,1,1,1,-1],
[1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,-1,1,1,1,1,1],
[-1,1,1,1,0,1,1,1,1,1,1,1,-1,1,1,-1,1,-1,1,1],
[1,1,1,1,1,-1,-1,1,1,1,-1,1,-1,1,-1,1,1,1,-1,-1],
[1,1,1,1,1,-1,1,1,1,1,1,1,1,-1,1,1,1,1,-1,1],
[1,1,1,1,-1,1,1,1,1,1,1,-1,1,1,1,1,-1,1,1,1],
[1,1,1,1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-1],
[-1,1,1,1,1,1,1,-1,1,-1,1,-1,1,1,1,1,1,1,1,-1],
[1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1],
[-1,1,-1,1,-1,-1,-1,1,1,1,1,-1,-1,1,-1,1,0,1,1,1],
[-1,1,1,1,1,1,1,1,1,1,1,-1,1,1,1,-1,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,1,1,-1,1,1,-1,1,1,-1,-1],
[1,1,1,1,1,1,1,1,-1,1,1,1,1,1,1,1,1,1,1,1],
[0,1,1,-1,1,1,1,1,-1,1,-1,1,1,1,-1,-1,-1,1,1,1],
[1,-1,1,1,1,-1,1,1,1,-1,1,-1,1,1,1,1,1,1,-1,1],
[1,1,1,-1,1,1,1,-1,1,1,1,1,1,-1,1,1,1,1,1,1],
[1,1,1,1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,1,-1,1,1,-1,1,1,1,1,-1,1,1,1,1,1,1,-1,0,1],
[-1,1,1,1,1,1,1,1,1,1,1,1,1,1,-1,1,1,1,-1,1]
])