Skip to main content

Flipkart

Flipkart OA 2023 - Robots and Warehouse Goods


An e-commerce company's warehouse is represented as an N x M grid in the company's system. Each cell in the grid represents a storage unit where goods are kept. The value of each cell indicates the total count of goods present in that cell.

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

From any position (a, b) in the grid, both robots can move to the next row:

  • (a+1, b): straight down.
  • (a+1, b-1): down-left.
  • (a+1, b+1): down-right.

If both robots land in the same cell, only one of them can pick the goods from that cell. After goods in a cell are picked, the value of that cell becomes zero in the system.

Write an algorithm to determine the maximum number of goods that both robots can pick up.

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.

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

Constraints:

  • 2 <= numRows, numCols <= 50