Flipkart OA-4 2023

Problem Description

An e-commerce company’s warehouse is represented as an N x M grid in their system. Each cell in the grid represents a storage unit where goods are stored, and the value of each cell indicates the total count of goods in that unit.

• Robot 1 starts at the top-left corner of the grid, positioned at (0, 0).
• Robot 2 starts at the top-right corner of the grid, positioned at (0, M-1).

From any cell (a, b) in the grid, both robots can move to the next row in one of three ways:

1. (a+1, b): Move directly down.
2. (a+1, b-1): Move down-left.
3. (a+1, b+1): Move down-right.

If both robots land on the same cell, only one of them can pick up the goods in that cell. Once goods from a cell are collected, the cell’s value is set to zero in the system.

Design an algorithm to calculate the maximum number of goods that both robots can collect.

Input Format:

• The first line contains two space-separated integers:
  • numRows: Total number of rows (N).
  • numCols: Total number of columns (M).
• The next N lines each contain M space-separated integers representing the count of goods in each cell of the warehouse.

Output Format:

• Print a single integer representing the maximum number of goods that can be picked by both robots.

Constraints:

2 <= numRows, numCols <= 50

Example:

Input:

3 4
3 2 2 1
6 2 3 4
4 7 6 8

Output:

29

Explanation:

• Robot 1 starts at position (0,0) and Robot 2 starts at position (0,3).
• Robot 1's Path: (0,0) → (1,0) → (2,1)
  • Total goods collected by Robot 1: 3 + 6 + 7 = 16
• Robot 2's Path: (0,3) → (1,3) → (2,3)
  • Total goods collected by Robot 2: 1 + 4 + 8 = 13
• Total goods collected = 16 + 13 = 29