Maximizing Chocolates in Grid using 2 robots (Chocolates Pickup)
Given a 2D array grid[][] of size R X C, such that grid[i][j] represents the number of chocolates that you can collect from the (i, j) cell. We have two robots that can collect the chocolates: Robot #1 is located at the top-left corner (0, 0), and Robot #2 is located at the top-right corner (0, cols โ 1). Return the maximum number of chocolates we can collect using both robots by following the rules below:
- From a cell (i, j), robots can move to cell (i + 1, j โ 1), (i + 1, j), or (i + 1, j + 1).
- When any robot passes through a cell, It picks up all chocolates, and the cell becomes an empty cell.
- When both robots stay in the same cell, only one takes the chocolates.
- Both robots cannot move outside of the grid at any moment.
- Both robots should reach the bottom row in grid.
Examples:
Input: R = 4, C = 3, grid[][]= {{4, 1, 2}, {3, 6, 1}, {1, 6, 6}, {3, 1, 2}}
Output: 32
Explanation:
- The path followed by first robot is: (0, 0) -> (1, 0) -> (2, 1) -> (3, 0), so total chocolates collected: 4 + 3 + 6 + 3 = 16
- The path followed by second robot is: (0, 2) -> (1, 1) -> (2, 2) -> (3, 2), so total chocolates connected: 2 + 6 + 6 + 2 = 16
Total Chocolates collected by both the robots: 16 + 16 = 32
Input: R = 5, C = 7, grid[][] = {{2, 0, 0, 0, 0, 0, 2}, {2, 1, 0, 0, 0, 4, 0}, {2, 0, 10, 0, 1, 0, 0}, {0, 3, 0, 6, 5, 0, 0}, {1, 0, 3, 4, 0, 0, 6}}
Output: 38
Explanation:
- The path followed by first robot is: (0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> (4, 2), so total chocolates collected: 2 + 1 + 10 + 6 + 3 = 22
- The path followed by second robot is: (0, 6) -> (1, 5) -> (2, 4) -> (3, 4) -> (4, 3), so total chocolates collected: 2 + 4 + 1 + 5 + 4 = 16
Total Chocolates collected by both the robots: 22 + 16 = 38
Approach: The problem can be solved using the following approach:
The problem can be solved using Dynamic Programming. The idea is to keep track of the positions of both robots at any time. Since both robots move downwards at each step, they will always be on the same row. Therefore, we can use a 3D dynamic programming table dp[][][] where dp[i][j1][j2] represents the maximum number of chocolates that can be collected when the robots are at cells (i, j1) and (i, j2).
Steps to solve the problem:
- Maintain a recursive function, say calculateMaxChocolates(row, col1, col2) which takes the current row, column of robot1 and column of robot2 as arguments and returns the maximum chocolates that can be collected if the robot1 starts from (row, column1) and robot2 starts from (row, column2).
- Check if any of the robot moves out of the grid then return a very large negative value.
- For all the cells inside the grid, explore all the 9 cases for both the robots: (row + 1, col1 โ 1, col2 โ 1), (row + 1, col1 โ 1, col2), (row + 1, col1 โ 1, col2 + 1), (row + 1, col1, col2 โ 1), (row + 1, col1, col2), (row + 1, col1, col2 + 1), (row + 1, col1 + 1, col2 โ 1), (row + 1, col1 + 1, col2) and (row + 1, col1 + 1, col2 + 1).
- Get the maximum chocolates collected by both the robots over all the cases to get the final answer.
Below is the implementation of the above approach:
C++14
#include <iostream> #include <vector> using namespace std; // Function to calculate the maximum number of chocolates // that can be collected int calculateMaxChocolates( int currentRow, int robot1Col, int robot2Col, int totalRows, int totalCols, vector<vector< int > >& chocolateGrid, vector<vector<vector< int > > >& dp) { // If either robot is out of the grid, return a large // negative number if (robot1Col < 0 || robot1Col >= totalCols || robot2Col < 0 || robot2Col >= totalCols) return -1e8; // If robots have reached the bottom row if (currentRow == totalRows - 1) { // If both robots are in the same cell, return // chocolates in that cell if (robot1Col == robot2Col) return chocolateGrid[currentRow][robot1Col]; // Else, return sum of chocolates in both cells else return chocolateGrid[currentRow][robot1Col] + chocolateGrid[currentRow][robot2Col]; } // If this state has been computed before, return the // stored result if (dp[currentRow][robot1Col][robot2Col] != -1) return dp[currentRow][robot1Col][robot2Col]; // Initialize the maximum chocolates that can be // collected from this state int maxChocolates = -1e8; // Explore all possible moves for both robots for ( int dRobot1 = -1; dRobot1 <= 1; dRobot1++) { for ( int dRobot2 = -1; dRobot2 <= 1; dRobot2++) { int chocolates = 0; // If both robots are in the same cell, only one // robot collects the chocolates if (robot1Col == robot2Col) chocolates = chocolateGrid[currentRow][robot1Col]; // Else, both robots collect chocolates else chocolates = chocolateGrid[currentRow][robot1Col] + chocolateGrid[currentRow] [robot2Col]; // Add the chocolates collected in the next // state chocolates += calculateMaxChocolates( currentRow + 1, robot1Col + dRobot1, robot2Col + dRobot2, totalRows, totalCols, chocolateGrid, dp); // Update the maximum chocolates that can be // collected maxChocolates = max(maxChocolates, chocolates); } } // Store the result and return return dp[currentRow][robot1Col][robot2Col] = maxChocolates; } int main() { // Provided input int totalRows = 4, totalCols = 3; vector<vector< int > > chocolateGrid = { {4, 1, 2}, {3, 6, 1}, {1, 6, 6}, {3, 1, 2} }; // Initialize the dp table with -1 vector<vector<vector< int > > > dp( totalRows, vector<vector< int > >(totalCols, vector< int >(totalCols, -1))); // Calculate the result int result = calculateMaxChocolates( 0, 0, totalCols - 1, totalRows, totalCols, chocolateGrid, dp); // Output the result cout << "The maximum number of chocolates that can be " "collected is: " << result << endl; return 0; } |
Java
public class ChocolateGrid { static int calculateMaxChocolates( int currentRow, int robot1Col, int robot2Col, int totalRows, int totalCols, int [][] chocolateGrid, int [][][] dp) { // If either robot is out of the grid, return a large negative number if (robot1Col < 0 || robot1Col >= totalCols || robot2Col < 0 || robot2Col >= totalCols) { return - 10000000 ; } // If robots have reached the bottom row if (currentRow == totalRows - 1 ) { // If both robots are in the same cell, return chocolates in that cell if (robot1Col == robot2Col) { return chocolateGrid[currentRow][robot1Col]; } // Else, return sum of chocolates in both cells else { return chocolateGrid[currentRow][robot1Col] + chocolateGrid[currentRow][robot2Col]; } } // If this state has been computed before, return the stored result if (dp[currentRow][robot1Col][robot2Col] != - 1 ) { return dp[currentRow][robot1Col][robot2Col]; } // Initialize the maximum chocolates that can be collected from this state int maxChocolates = - 10000000 ; // Explore all possible moves for both robots for ( int dRobot1 = - 1 ; dRobot1 <= 1 ; dRobot1++) { for ( int dRobot2 = - 1 ; dRobot2 <= 1 ; dRobot2++) { int chocolates = 0 ; // If both robots are in the same cell, only one robot collects the chocolates if (robot1Col == robot2Col) { chocolates = chocolateGrid[currentRow][robot1Col]; } // Else, both robots collect chocolates else { chocolates = chocolateGrid[currentRow][robot1Col] + chocolateGrid[currentRow][robot2Col]; } // Add the chocolates collected in the next state chocolates += calculateMaxChocolates( currentRow + 1 , robot1Col + dRobot1, robot2Col + dRobot2, totalRows, totalCols, chocolateGrid, dp ); // Update the maximum chocolates that can be collected maxChocolates = Math.max(maxChocolates, chocolates); } } // Store the result and return dp[currentRow][robot1Col][robot2Col] = maxChocolates; return maxChocolates; } public static void main(String[] args) { int totalRows = 4 ; int totalCols = 3 ; int [][] chocolateGrid = { { 4 , 1 , 2 }, { 3 , 6 , 1 }, { 1 , 6 , 6 }, { 3 , 1 , 2 } }; // Initialize the dp table with -1 int [][][] dp = new int [totalRows][totalCols][totalCols]; for ( int i = 0 ; i < totalRows; i++) { for ( int j = 0 ; j < totalCols; j++) { for ( int k = 0 ; k < totalCols; k++) { dp[i][j][k] = - 1 ; } } } int result = calculateMaxChocolates( 0 , 0 , totalCols - 1 , totalRows, totalCols, chocolateGrid, dp); System.out.println( "The maximum number of chocolates that can be collected is: " + result); } } |
Python3
def calculate_max_chocolates(current_row, robot1_col, robot2_col, total_rows, total_cols, chocolate_grid, dp): # If either robot is out of the grid, return a large negative number if robot1_col < 0 or robot1_col > = total_cols or robot2_col < 0 or robot2_col > = total_cols: return - 1e8 # If robots have reached the bottom row if current_row = = total_rows - 1 : # If both robots are in the same cell, return chocolates in that cell if robot1_col = = robot2_col: return chocolate_grid[current_row][robot1_col] # Else, return sum of chocolates in both cells else : return chocolate_grid[current_row][robot1_col] + chocolate_grid[current_row][robot2_col] # If this state has been computed before, return the stored result if dp[current_row][robot1_col][robot2_col] ! = - 1 : return dp[current_row][robot1_col][robot2_col] # Initialize the maximum chocolates that can be collected from this state max_chocolates = - 1e8 # Explore all possible moves for both robots for d_robot1 in range ( - 1 , 2 ): for d_robot2 in range ( - 1 , 2 ): chocolates = 0 # If both robots are in the same cell, only one robot collects the chocolates if robot1_col = = robot2_col: chocolates = chocolate_grid[current_row][robot1_col] # Else, both robots collect chocolates else : chocolates = chocolate_grid[current_row][robot1_col] + chocolate_grid[current_row][robot2_col] # Add the chocolates collected in the next state chocolates + = calculate_max_chocolates( current_row + 1 , robot1_col + d_robot1, robot2_col + d_robot2, total_rows, total_cols, chocolate_grid, dp ) # Update the maximum chocolates that can be collected max_chocolates = max (max_chocolates, chocolates) # Store the result and return dp[current_row][robot1_col][robot2_col] = max_chocolates return max_chocolates if __name__ = = "__main__" : # Provided input total_rows, total_cols = 4 , 3 chocolate_grid = [ [ 4 , 1 , 2 ], [ 3 , 6 , 1 ], [ 1 , 6 , 6 ], [ 3 , 1 , 2 ] ] # Initialize the dp table with -1 dp = [[[ - 1 for _ in range (total_cols)] for _ in range (total_cols)] for _ in range (total_rows)] # Calculate the result result = calculate_max_chocolates( 0 , 0 , total_cols - 1 , total_rows, total_cols, chocolate_grid, dp) # Output the result print (f "The maximum number of chocolates that can be collected is: {result}" ) |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to calculate the maximum number of // chocolates that can be collected static int CalculateMaxChocolates( int currentRow, int robot1Col, int robot2Col, int totalRows, int totalCols, List<List< int > > chocolateGrid, List<List<List< int > > > dp) { // If either robot is out of the grid, return a // large negative number if (robot1Col < 0 || robot1Col >= totalCols || robot2Col < 0 || robot2Col >= totalCols) return int .MinValue; // If robots have reached the bottom row if (currentRow == totalRows - 1) { // If both robots are in the same cell, return // chocolates in that cell if (robot1Col == robot2Col) return chocolateGrid[currentRow][robot1Col]; // Else, return sum of chocolates in both cells else return chocolateGrid[currentRow][robot1Col] + chocolateGrid[currentRow][robot2Col]; } // If this state has been computed before, return // the stored result if (dp[currentRow][robot1Col][robot2Col] != -1) return dp[currentRow][robot1Col][robot2Col]; // Initialize the maximum chocolates that can be // collected from this state int maxChocolates = int .MinValue; // Explore all possible moves for both robots for ( int dRobot1 = -1; dRobot1 <= 1; dRobot1++) { for ( int dRobot2 = -1; dRobot2 <= 1; dRobot2++) { int chocolates = 0; // If both robots are in the same cell, only // one robot collects the chocolates if (robot1Col == robot2Col) chocolates = chocolateGrid[currentRow] [robot1Col]; // Else, both robots collect chocolates else chocolates = chocolateGrid[currentRow] [robot1Col] + chocolateGrid[currentRow] [robot2Col]; // Add the chocolates collected in the next // state chocolates += CalculateMaxChocolates( currentRow + 1, robot1Col + dRobot1, robot2Col + dRobot2, totalRows, totalCols, chocolateGrid, dp); // Update the maximum chocolates that can be // collected maxChocolates = Math.Max(maxChocolates, chocolates); } } // Store the result and return return dp[currentRow][robot1Col][robot2Col] = maxChocolates; } static void Main() { // Provided input int totalRows = 4, totalCols = 3; List<List< int > > chocolateGrid = new List<List< int > >{ new List< int >{ 4, 1, 2 }, new List< int >{ 3, 6, 1 }, new List< int >{ 1, 6, 6 }, new List< int >{ 3, 1, 2 } }; // Initialize the dp table with -1 List<List<List< int > > > dp = new List<List<List< int > > >(); for ( int i = 0; i < totalRows; i++) { dp.Add( new List<List< int > >()); for ( int j = 0; j < totalCols; j++) { dp[i].Add( new List< int >()); for ( int k = 0; k < totalCols; k++) { dp[i][j].Add(-1); } } } // Calculate the result int result = CalculateMaxChocolates( 0, 0, totalCols - 1, totalRows, totalCols, chocolateGrid, dp); // Output the result Console.WriteLine( "The maximum number of chocolates that can be collected is: " + result); } } // This code is contributed by Susobhan Akhuli |
Javascript
// JavaScript Implementation function calculateMaxChocolates(currentRow, robot1Col, robot2Col, totalRows, totalCols, chocolateGrid, dp) { // If either robot is out of the grid, return a large negative number if (robot1Col < 0 || robot1Col >= totalCols || robot2Col < 0 || robot2Col >= totalCols) { return -1e8; } // If robots have reached the bottom row if (currentRow === totalRows - 1) { // If both robots are in the same cell, return chocolates in that cell if (robot1Col === robot2Col) { return chocolateGrid[currentRow][robot1Col]; } else { // Else, return sum of chocolates in both cells return chocolateGrid[currentRow][robot1Col] + chocolateGrid[currentRow][robot2Col]; } } // If this state has been computed before, return the stored result if (dp[currentRow][robot1Col][robot2Col] !== -1) { return dp[currentRow][robot1Col][robot2Col]; } // Initialize the maximum chocolates that can be collected from this state let maxChocolates = -1e8; // Explore all possible moves for both robots for (let dRobot1 = -1; dRobot1 <= 1; dRobot1++) { for (let dRobot2 = -1; dRobot2 <= 1; dRobot2++) { let chocolates = 0; // If both robots are in the same cell, only one robot collects the chocolates if (robot1Col === robot2Col) { chocolates = chocolateGrid[currentRow][robot1Col]; } else { // Else, both robots collect chocolates chocolates = chocolateGrid[currentRow][robot1Col] + chocolateGrid[currentRow][robot2Col]; } // Add the chocolates collected in the next state chocolates += calculateMaxChocolates(currentRow + 1, robot1Col + dRobot1, robot2Col + dRobot2, totalRows, totalCols, chocolateGrid, dp); // Update the maximum chocolates that can be collected maxChocolates = Math.max(maxChocolates, chocolates); } } // Store the result and return dp[currentRow][robot1Col][robot2Col] = maxChocolates; return maxChocolates; } // Provided input const totalRows = 4; const totalCols = 3; const chocolateGrid = [ [4, 1, 2], [3, 6, 1], [1, 6, 6], [3, 1, 2] ]; // Initialize the dp table with -1 const dp = Array.from({ length: totalRows }, () => Array.from({ length: totalCols }, () => Array(totalCols).fill(-1)) ); // Calculate the result const result = calculateMaxChocolates(0, 0, totalCols - 1, totalRows, totalCols, chocolateGrid, dp); // Output the result console.log(`The maximum number of chocolates that can be collected is: ${result}`); // This code is contributed by Sakshi |
The maximum number of chocolates that can be collected is: 32
Time complexity: O(R * C * C), where R is the number of rows and C is the number of columns in the input 2D array grid[][].
Auxiliary Space: O(R * C * C)