We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Maximum Number of Fruits Collected

Number: 3648

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an n x n grid (dungeon) in which each cell holds a certain number of fruits, three children start in three different corners: (0, 0), (0, n - 1) and (n - 1, 0). Each child is required to make exactly n – 1 moves following their own allowed directions. The allowed moves are as follows: • Child 1 (from (0, 0)): may move right, down, or diagonally down‐right. • Child 2 (from (0, n - 1)): may move down, diagonally down‐left, or diagonally down‐right. • Child 3 (from (n - 1, 0)): may move right, up‐right, or diagonally down‐right. All three must reach room (n – 1, n – 1) after exactly n – 1 moves. When a child enters a room, they pick up all fruits in that room; if multiple children visit the same room, the fruits are collected only once. The problem asks for the maximum total number of fruits the children can collect.

Key Insights

  • This is a multi-agent path planning problem that resembles the well-known “Cherry Pickup” but for three agents with different allowed moves.
  • All children move exactly n – 1 times and must finish at the same destination; hence their movements can be regarded as synchronized rounds even though the effect on coordinates differs.
  • For each move, every child has exactly three choices (their allowed moves), so there are 27 combined transitions per “round.”
  • To avoid double‐counting fruits when two or more children land on the same cell, add the fruit value only once when they converge.
  • A recursion with memoization (or bottom‐up dynamic programming) is necessary to try and merge all three paths while ensuring that invalid states (out‐of‐bound moves) are pruned.

Space and Time Complexity

Time Complexity: In the worst case the state is defined by the positions of three children. A naïve DP state has up to O(n^6) possibilities and each state branches to 27 transitions. (In practice, using synchronizing moves and pruning invalid states reduces the practical state space, but the theoretical worst‐case is very large.) Space Complexity: O(n^6) for the memoization cache in the worst case, plus recursion stack overhead.

Solution

We solve the problem using a recursive dynamic programming approach with memoization. We define a recursive helper function that takes the current positions (r1, c1) for child 1, (r2, c2) for child 2, and (r3, c3) for child 3. At each step, for every possible move for each child (based on their allowed moves), we compute the new positions, check that they are within bounds and eventually match the target (n – 1, n – 1) when the moves are complete. For the fruits collected in the current step, we add the fruit value at each visited cell, ensuring that if two or more children land on the same cell the fruit is only added once. The recursion returns the maximum fruits that can be collected from the current state to the end. The calculated value for a state is cached in a memo dictionary so that if the same state is reached again, the stored result is reused.

The allowed moves for each child are: • Child 1: (r+1, c),(r, c+1), (r+1, c+1) • Child 2: (r+1, c), (r+1, c-1), (r+1, c+1) • Child 3: (r-1, c+1), (r, c+1), (r+1, c+1)

This recursive formulation (or equivalently a DP formulation) traverses all possible move combinations and collects the maximum result.

Code Solutions

# Python solution with detailed comments

def maxFruits(fruits):
    n = len(fruits)
    
    # Allowed moves for each child
    moves1 = [(1, 0), (0, 1), (1, 1)]
    moves2 = [(1, 0), (1, -1), (1, 1)]
    moves3 = [(-1, 1), (0, 1), (1, 1)]
    
    # memoization dictionary to save computed states
    memo = {}
    
    # Recursive function: positions for child1 (r1, c1), child2 (r2, c2), child3 (r3, c3)
    def dp(r1, c1, r2, c2, r3, c3):
        # If all three have reached the destination, return fruits there (only once)
        if r1 == r2 == r3 == n - 1 and c1 == c2 == c3 == n - 1:
            return fruits[n - 1][n - 1]
            
        # Create a key based on current positions
        key = (r1, c1, r2, c2, r3, c3)
        if key in memo:
            return memo[key]
        
        # Compute fruits collected in the current room(s); count each cell only once
        collected = 0
        seen = set()
        for (r, c) in [(r1, c1), (r2, c2), (r3, c3)]:
            if (r, c) not in seen:
                collected += fruits[r][c]
                seen.add((r, c))
                
        best = float('-inf')
        # Iterate over all possible moves for child1, child2 and child3
        for dr1, dc1 in moves1:
            nr1, nc1 = r1 + dr1, c1 + dc1
            if not (0 <= nr1 < n and 0 <= nc1 < n):
                continue
            for dr2, dc2 in moves2:
                nr2, nc2 = r2 + dr2, c2 + dc2
                if not (0 <= nr2 < n and 0 <= nc2 < n):
                    continue
                for dr3, dc3 in moves3:
                    nr3, nc3 = r3 + dr3, c3 + dc3
                    if not (0 <= nr3 < n and 0 <= nc3 < n):
                        continue
                    best = max(best, dp(nr1, nc1, nr2, nc2, nr3, nc3))
        
        memo[key] = collected + (best if best != float('-inf') else 0)
        return memo[key]
    
    # Start recursion from the three starting positions
    # Starting positions: child1: (0,0), child2: (0, n-1), child3: (n-1, 0)
    return dp(0, 0, 0, n - 1, n - 1, 0)

# Example usage:
print(maxFruits([[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]))
← Back to All Questions