Skip to content

3363. Find the Maximum Number of Fruits Collected

Description

There is a game dungeon comprised of n x n rooms arranged in a grid.

You are given a 2D array fruits of size n x n, where fruits[i][j] represents the number of fruits in the room (i, j). Three children will play in the game dungeon, with initial positions at the corner rooms (0, 0), (0, n - 1), and (n - 1, 0).

The children will make exactly n - 1 moves according to the following rules to reach the room (n - 1, n - 1):

  • The child starting from (0, 0) must move from their current room (i, j) to one of the rooms (i + 1, j + 1), (i + 1, j), and (i, j + 1) if the target room exists.
  • The child starting from (0, n - 1) must move from their current room (i, j) to one of the rooms (i + 1, j - 1), (i + 1, j), and (i + 1, j + 1) if the target room exists.
  • The child starting from (n - 1, 0) must move from their current room (i, j) to one of the rooms (i - 1, j + 1), (i, j + 1), and (i + 1, j + 1) if the target room exists.

When a child enters a room, they will collect all the fruits there. If two or more children enter the same room, only one child will collect the fruits, and the room will be emptied after they leave.

Return the maximum number of fruits the children can collect from the dungeon.

 

Example 1:

Input: fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]

Output: 100

Explanation:

In this example:

  • The 1st child (green) moves on the path (0,0) -> (1,1) -> (2,2) -> (3, 3).
  • The 2nd child (red) moves on the path (0,3) -> (1,2) -> (2,3) -> (3, 3).
  • The 3rd child (blue) moves on the path (3,0) -> (3,1) -> (3,2) -> (3, 3).

In total they collect 1 + 6 + 11 + 16 + 4 + 8 + 12 + 13 + 14 + 15 = 100 fruits.

Example 2:

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

Output: 4

Explanation:

In this example:

  • The 1st child moves on the path (0,0) -> (1,1).
  • The 2nd child moves on the path (0,1) -> (1,1).
  • The 3rd child moves on the path (1,0) -> (1,1).

In total they collect 1 + 1 + 1 + 1 = 4 fruits.

 

Constraints:

  • 2 <= n == fruits.length == fruits[i].length <= 1000
  • 0 <= fruits[i][j] <= 1000

Solutions

Solution 1: Dynamic Programming

According to the problem description, for the child starting from \((0, 0)\) to reach \((n - 1, n - 1)\) in exactly \(n - 1\) steps, they can only move through the rooms on the main diagonal \((i, i)\), where \(i = 0, 1, \ldots, n - 1\). The child starting from \((0, n - 1)\) can only move through rooms above the main diagonal, while the child starting from \((n - 1, 0)\) can only move through rooms below the main diagonal. This means that except for reaching the destination at \((n - 1, n - 1)\), no other rooms will be visited by multiple children.

We can use dynamic programming to calculate the number of fruits that the children starting from \((0, n - 1)\) and \((n - 1, 0)\) can collect when reaching \((i, j)\). Define \(f[i][j]\) as the number of fruits a child can collect when reaching \((i, j)\).

For the child starting from \((0, n - 1)\), the state transition equation is:

\[ f[i][j] = \max(f[i - 1][j], f[i - 1][j - 1], f[i - 1][j + 1]) + \text{fruits}[i][j] \]

Note that \(f[i - 1][j + 1]\) is only valid when \(j + 1 < n\).

For the child starting from \((n - 1, 0)\), the state transition equation is:

\[ f[i][j] = \max(f[i][j - 1], f[i - 1][j - 1], f[i + 1][j - 1]) + \text{fruits}[i][j] \]

Similarly, \(f[i + 1][j - 1]\) is only valid when \(i + 1 < n\).

Finally, the answer is \(\sum_{i=0}^{n-1} \text{fruits}[i][i] + f[n-2][n-1] + f[n-1][n-2]\), which is the sum of fruits on the main diagonal plus the fruits that the two children can collect when reaching \((n - 2, n - 1)\) and \((n - 1, n - 2)\).

The time complexity is \(O(n^2)\), and the space complexity is \(O(n^2)\), where \(n\) is the side length of the room grid.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
        n = len(fruits)
        f = [[-inf] * n for _ in range(n)]
        f[0][n - 1] = fruits[0][n - 1]
        for i in range(1, n):
            for j in range(i + 1, n):
                f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + fruits[i][j]
                if j + 1 < n:
                    f[i][j] = max(f[i][j], f[i - 1][j + 1] + fruits[i][j])
        f[n - 1][0] = fruits[n - 1][0]
        for j in range(1, n):
            for i in range(j + 1, n):
                f[i][j] = max(f[i][j - 1], f[i - 1][j - 1]) + fruits[i][j]
                if i + 1 < n:
                    f[i][j] = max(f[i][j], f[i + 1][j - 1] + fruits[i][j])
        return sum(fruits[i][i] for i in range(n)) + f[n - 2][n - 1] + f[n - 1][n - 2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int maxCollectedFruits(int[][] fruits) {
        int n = fruits.length;
        final int inf = 1 << 29;
        int[][] f = new int[n][n];
        for (var row : f) {
            Arrays.fill(row, -inf);
        }
        f[0][n - 1] = fruits[0][n - 1];
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - 1]) + fruits[i][j];
                if (j + 1 < n) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j + 1] + fruits[i][j]);
                }
            }
        }
        f[n - 1][0] = fruits[n - 1][0];
        for (int j = 1; j < n; j++) {
            for (int i = j + 1; i < n; i++) {
                f[i][j] = Math.max(f[i][j - 1], f[i - 1][j - 1]) + fruits[i][j];
                if (i + 1 < n) {
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + fruits[i][j]);
                }
            }
        }
        int ans = f[n - 2][n - 1] + f[n - 1][n - 2];
        for (int i = 0; i < n; i++) {
            ans += fruits[i][i];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int maxCollectedFruits(vector<vector<int>>& fruits) {
        int n = fruits.size();
        const int inf = 1 << 29;
        vector<vector<int>> f(n, vector<int>(n, -inf));

        f[0][n - 1] = fruits[0][n - 1];
        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + fruits[i][j];
                if (j + 1 < n) {
                    f[i][j] = max(f[i][j], f[i - 1][j + 1] + fruits[i][j]);
                }
            }
        }

        f[n - 1][0] = fruits[n - 1][0];
        for (int j = 1; j < n; j++) {
            for (int i = j + 1; i < n; i++) {
                f[i][j] = max(f[i][j - 1], f[i - 1][j - 1]) + fruits[i][j];
                if (i + 1 < n) {
                    f[i][j] = max(f[i][j], f[i + 1][j - 1] + fruits[i][j]);
                }
            }
        }

        int ans = f[n - 2][n - 1] + f[n - 1][n - 2];
        for (int i = 0; i < n; i++) {
            ans += fruits[i][i];
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func maxCollectedFruits(fruits [][]int) int {
    n := len(fruits)
    const inf = 1 << 29
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, n)
        for j := range f[i] {
            f[i][j] = -inf
        }
    }

    f[0][n-1] = fruits[0][n-1]
    for i := 1; i < n; i++ {
        for j := i + 1; j < n; j++ {
            f[i][j] = max(f[i-1][j], f[i-1][j-1]) + fruits[i][j]
            if j+1 < n {
                f[i][j] = max(f[i][j], f[i-1][j+1]+fruits[i][j])
            }
        }
    }

    f[n-1][0] = fruits[n-1][0]
    for j := 1; j < n; j++ {
        for i := j + 1; i < n; i++ {
            f[i][j] = max(f[i][j-1], f[i-1][j-1]) + fruits[i][j]
            if i+1 < n {
                f[i][j] = max(f[i][j], f[i+1][j-1]+fruits[i][j])
            }
        }
    }

    ans := f[n-2][n-1] + f[n-1][n-2]
    for i := 0; i < n; i++ {
        ans += fruits[i][i]
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function maxCollectedFruits(fruits: number[][]): number {
    const n = fruits.length;
    const inf = 1 << 29;
    const f: number[][] = Array.from({ length: n }, () => Array(n).fill(-inf));

    f[0][n - 1] = fruits[0][n - 1];
    for (let i = 1; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - 1]) + fruits[i][j];
            if (j + 1 < n) {
                f[i][j] = Math.max(f[i][j], f[i - 1][j + 1] + fruits[i][j]);
            }
        }
    }

    f[n - 1][0] = fruits[n - 1][0];
    for (let j = 1; j < n; j++) {
        for (let i = j + 1; i < n; i++) {
            f[i][j] = Math.max(f[i][j - 1], f[i - 1][j - 1]) + fruits[i][j];
            if (i + 1 < n) {
                f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + fruits[i][j]);
            }
        }
    }

    let ans = f[n - 2][n - 1] + f[n - 1][n - 2];
    for (let i = 0; i < n; i++) {
        ans += fruits[i][i];
    }

    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
impl Solution {
    pub fn max_collected_fruits(fruits: Vec<Vec<i32>>) -> i32 {
        let n = fruits.len();
        let inf = 1 << 29;
        let mut f = vec![vec![-inf; n]; n];

        f[0][n - 1] = fruits[0][n - 1];
        for i in 1..n {
            for j in i + 1..n {
                f[i][j] = std::cmp::max(f[i - 1][j], f[i - 1][j - 1]) + fruits[i][j];
                if j + 1 < n {
                    f[i][j] = std::cmp::max(f[i][j], f[i - 1][j + 1] + fruits[i][j]);
                }
            }
        }

        f[n - 1][0] = fruits[n - 1][0];
        for j in 1..n {
            for i in j + 1..n {
                f[i][j] = std::cmp::max(f[i][j - 1], f[i - 1][j - 1]) + fruits[i][j];
                if i + 1 < n {
                    f[i][j] = std::cmp::max(f[i][j], f[i + 1][j - 1] + fruits[i][j]);
                }
            }
        }

        let mut ans = f[n - 2][n - 1] + f[n - 1][n - 2];
        for i in 0..n {
            ans += fruits[i][i];
        }

        ans
    }
}

Comments