Find the Maximum Number of Fruits Collected - Problem

Welcome to the Fruit Collection Adventure! Imagine three children exploring a magical n × n dungeon filled with delicious fruits. Each room (i, j) contains fruits[i][j] pieces of fruit waiting to be collected.

The three children start at different corners:

Child A: Top-left corner (0, 0)
Child B: Top-right corner (0, n-1)
Child C: Bottom-left corner (n-1, 0)

All three must reach the treasure room at (n-1, n-1) in exactly n-1 moves. Each child has specific movement rules:

Child A: Can move to (i+1, j+1), (i+1, j), or (i, j+1) (diagonal, down, or right)
Child B: Can move to (i+1, j-1), (i+1, j), or (i+1, j+1) (down-left, down, or down-right)
Child C: Can move to (i-1, j+1), (i, j+1), or (i+1, j+1) (up-right, right, or down-right)

Important rule: If multiple children enter the same room, only one gets the fruits! Your goal is to find the maximum total fruits they can collect by choosing optimal paths.

Input & Output

example_1.py — Basic 3x3 Grid

$ Input: fruits = [[1,2,3],[4,5,6],[7,8,9]]

› Output: 24

💡 Note: Child A: (0,0)→(1,1)→(2,2) collects 1+5+9=15. Child B: (0,2)→(1,2)→(2,2) would collect 3+6, but (2,2) already taken. Child C: (2,0)→(2,1)→(2,2) would collect 7+8, but (2,2) already taken. Optimal paths give total 24 fruits.

example_2.py — Symmetric Grid

$ Input: fruits = [[1,1,1],[1,1,1],[1,1,1]]

› Output: 7

💡 Note: All cells have 1 fruit. Three children must coordinate to visit 7 unique cells total to reach (2,2), collecting 7 fruits maximum.

example_3.py — Edge Case 2x2

$ Input: fruits = [[5,10],[15,20]]

› Output: 50

💡 Note: Child A: (0,0)→(1,1) gets 5+20=25. Child B: (0,1)→(1,1) gets 10 (can't get (1,1) again). Child C: (1,0)→(1,1) gets 15 (can't get (1,1) again). Total: 5+10+15+20=50.

Constraints

2 ≤ n ≤ 20
0 ≤ fruits[i][j] ≤ 1000
All three children must reach (n-1, n-1) in exactly n-1 moves
Movement constraints differ for each child
When multiple children occupy same cell, only one collects fruits

Visualization

Tap to expand

Asked in

G Google 35 f Meta 28 a Amazon 22 ⊞ Microsoft 18

This problem requires 3D Dynamic Programming where we track all three children's positions simultaneously. The optimal approach uses memoization with state (step, pos1, pos2, pos3) and handles fruit collection conflicts using set operations. Time complexity is O(n⁶) but much faster than brute force due to avoiding redundant calculations.

Common Approaches

✓ Greedy

⏱️ Time: N/A Space: N/A

Dynamic Programming (3D State Space)

⏱️ Time: O(n^6) Space: O(n^6)

This optimal approach uses dynamic programming with a 3D state space where each state represents the positions of all three children. We memoize results to avoid recomputing the same subproblems.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int paths[3][1000][50][2]; // [child][path_idx][step][i,j]
static int path_lengths[3][1000];
static int num_paths[3];
static int n;
static int fruits[20][20];

void dfsA(int i, int j, int path_idx, int step) {
    paths[0][path_idx][step][0] = i;
    paths[0][path_idx][step][1] = j;
    
    if (i == n-1 && j == n-1) {
        path_lengths[0][path_idx] = step + 1;
        num_paths[0]++;
        return;
    }
    
    int next_path = num_paths[0];
    
    // Move diagonal (i+1, j+1)
    if (i+1 < n && j+1 < n) {
        if (next_path < 1000) {
            for (int k = 0; k <= step; k++) {
                paths[0][next_path][k][0] = paths[0][path_idx][k][0];
                paths[0][next_path][k][1] = paths[0][path_idx][k][1];
            }
            dfsA(i+1, j+1, next_path, step+1);
            next_path = num_paths[0];
        }
    }
    
    // Move down (i+1, j)
    if (i+1 < n) {
        if (next_path < 1000) {
            for (int k = 0; k <= step; k++) {
                paths[0][next_path][k][0] = paths[0][path_idx][k][0];
                paths[0][next_path][k][1] = paths[0][path_idx][k][1];
            }
            dfsA(i+1, j, next_path, step+1);
            next_path = num_paths[0];
        }
    }
    
    // Move right (i, j+1)
    if (j+1 < n) {
        if (next_path < 1000) {
            for (int k = 0; k <= step; k++) {
                paths[0][next_path][k][0] = paths[0][path_idx][k][0];
                paths[0][next_path][k][1] = paths[0][path_idx][k][1];
            }
            dfsA(i, j+1, next_path, step+1);
        }
    }
}

void dfsB(int i, int j, int path_idx, int step) {
    paths[1][path_idx][step][0] = i;
    paths[1][path_idx][step][1] = j;
    
    if (i == n-1 && j == n-1) {
        path_lengths[1][path_idx] = step + 1;
        num_paths[1]++;
        return;
    }
    
    int next_path = num_paths[1];
    
    // Move down-left (i+1, j-1)
    if (i+1 < n && j-1 >= 0) {
        if (next_path < 1000) {
            for (int k = 0; k <= step; k++) {
                paths[1][next_path][k][0] = paths[1][path_idx][k][0];
                paths[1][next_path][k][1] = paths[1][path_idx][k][1];
            }
            dfsB(i+1, j-1, next_path, step+1);
            next_path = num_paths[1];
        }
    }
    
    // Move down (i+1, j)
    if (i+1 < n) {
        if (next_path < 1000) {
            for (int k = 0; k <= step; k++) {
                paths[1][next_path][k][0] = paths[1][path_idx][k][0];
                paths[1][next_path][k][1] = paths[1][path_idx][k][1];
            }
            dfsB(i+1, j, next_path, step+1);
            next_path = num_paths[1];
        }
    }
    
    // Move down-right (i+1, j+1)
    if (i+1 < n && j+1 < n) {
        if (next_path < 1000) {
            for (int k = 0; k <= step; k++) {
                paths[1][next_path][k][0] = paths[1][path_idx][k][0];
                paths[1][next_path][k][1] = paths[1][path_idx][k][1];
            }
            dfsB(i+1, j+1, next_path, step+1);
        }
    }
}

void dfsC(int i, int j, int path_idx, int step) {
    paths[2][path_idx][step][0] = i;
    paths[2][path_idx][step][1] = j;
    
    if (i == n-1 && j == n-1) {
        path_lengths[2][path_idx] = step + 1;
        num_paths[2]++;
        return;
    }
    
    int next_path = num_paths[2];
    
    // Move up-right (i-1, j+1)
    if (i-1 >= 0 && j+1 < n) {
        if (next_path < 1000) {
            for (int k = 0; k <= step; k++) {
                paths[2][next_path][k][0] = paths[2][path_idx][k][0];
                paths[2][next_path][k][1] = paths[2][path_idx][k][1];
            }
            dfsC(i-1, j+1, next_path, step+1);
            next_path = num_paths[2];
        }
    }
    
    // Move right (i, j+1)
    if (j+1 < n) {
        if (next_path < 1000) {
            for (int k = 0; k <= step; k++) {
                paths[2][next_path][k][0] = paths[2][path_idx][k][0];
                paths[2][next_path][k][1] = paths[2][path_idx][k][1];
            }
            dfsC(i, j+1, next_path, step+1);
            next_path = num_paths[2];
        }
    }
    
    // Move down-right (i+1, j+1)
    if (i+1 < n && j+1 < n) {
        if (next_path < 1000) {
            for (int k = 0; k <= step; k++) {
                paths[2][next_path][k][0] = paths[2][path_idx][k][0];
                paths[2][next_path][k][1] = paths[2][path_idx][k][1];
            }
            dfsC(i+1, j+1, next_path, step+1);
        }
    }
}

int calculateFruits(int pathA_idx, int pathB_idx, int pathC_idx) {
    int visited[20][20] = {0};
    int total = 0;
    
    // Add fruits from path A
    for (int s = 0; s < path_lengths[0][pathA_idx]; s++) {
        int i = paths[0][pathA_idx][s][0];
        int j = paths[0][pathA_idx][s][1];
        if (!visited[i][j]) {
            visited[i][j] = 1;
            total += fruits[i][j];
        }
    }
    
    // Add fruits from path B
    for (int s = 0; s < path_lengths[1][pathB_idx]; s++) {
        int i = paths[1][pathB_idx][s][0];
        int j = paths[1][pathB_idx][s][1];
        if (!visited[i][j]) {
            visited[i][j] = 1;
            total += fruits[i][j];
        }
    }
    
    // Add fruits from path C
    for (int s = 0; s < path_lengths[2][pathC_idx]; s++) {
        int i = paths[2][pathC_idx][s][0];
        int j = paths[2][pathC_idx][s][1];
        if (!visited[i][j]) {
            visited[i][j] = 1;
            total += fruits[i][j];
        }
    }
    
    return total;
}

int parseMatrix(char* line) {
    char* p = line;
    int matrix_n = 0;
    
    // Count rows
    while (*p) {
        if (*p == '[' && (p == line || *(p-1) == ',' || *(p-1) == '[')) {
            matrix_n++;
        }
        p++;
    }
    
    p = line;
    int row = 0, col = 0;
    char num[10];
    int numIdx = 0;
    
    while (*p && row < matrix_n) {
        if (*p >= '0' && *p <= '9') {
            num[numIdx++] = *p;
        } else if (numIdx > 0) {
            num[numIdx] = '\0';
            fruits[row][col++] = atoi(num);
            numIdx = 0;
            if (col == matrix_n) {
                col = 0;
                row++;
            }
        }
        p++;
    }
    
    if (numIdx > 0 && row < matrix_n && col < matrix_n) {
        num[numIdx] = '\0';
        fruits[row][col] = atoi(num);
    }
    
    return matrix_n;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    n = parseMatrix(line);
    
    // Initialize
    memset(num_paths, 0, sizeof(num_paths));
    
    // Generate all paths
    dfsA(0, 0, 0, 0);
    dfsB(0, n-1, 0, 0);
    dfsC(n-1, 0, 0, 0);
    
    int maxTotal = 0;
    
    // Try all combinations
    for (int a = 0; a < num_paths[0]; a++) {
        for (int b = 0; b < num_paths[1]; b++) {
            for (int c = 0; c < num_paths[2]; c++) {
                int total = calculateFruits(a, b, c);
                if (total > maxTotal) {
                    maxTotal = total;
                }
            }
        }
    }
    
    printf("%d\n", maxTotal);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

26.4K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen