Mercedes-Benz | Online Assessment | Push Boxes | Need suggestions
Rishabh Gupta
1150
Mercedes BenzDynamic ProgrammingInterview

Greetings everyone,

Problem Statement

You are given a grid with N rows and M columns. This grid contains some vacant spaces represented by 0 and boxes represented by 1. You are initially at cell (1,1), and at any cell, you can move either right or down. While moving right or down, you can push a box in the same direction as you are moving as long as all the boxes in front of you remain in the grid boundaries.

Task

Determine the number of ways to go from the cell (1,1) to the cell (N, M). Since the answer can be very large, so print the answer modulo 10^9 + 7.

Notes

  • Multiple boxes can also be pushed as long as all the boxes remain in grid boundaries.
  • The cells (1,1) and (N,M) can also be occupied by boxes initially which cannot be pushed in any way.
  • 1-based indexing is followed.

Example 1

Assumptions

  • T=1
  • N=2
  • M=2
  • A=[[0,1],[0,0]]

Approach

  • There is only one way to go from (1,1) to (2,2):
    • You can move down from (1,1) to (2,1) and then move right from (2,1) to (2,2).
  • You cannot move the box from (1,2) to the right as it will go outside the boundaries of the grid, and Hence, there is only 1 way of moving from (1,1) to (2,2).

Therefore, there is only one way and so the output is 1.

Example 2

  • N=4
  • M=4
  • A = [[0, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
    Output = 5

Approach

Given below are the two ways out of 5 possible ways for the given grid. Here, c represents your current position on the way to (4,4).

c 0 0 1    0 c 0 1     0 0 0 1     0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1
0 1 1 0    0 1 1 0     0 c 1 0     0 0 c 1    0 0 0 1    0 0 0 1    0 0 0 1
0 1 1 0    0 1 1 0     0 1 1 0     0 1 1 0    0 1 c 0    0 1 0 c    0 1 0 0
0 0 0 0    0 0 0 0     0 1 0 0     0 1 0 0    0 1 1 0    0 1 1 0    0 1 1 c
c 0 0 1    0 c 0 1     0 0 c 1     0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1
0 1 1 0    0 1 1 0     0 1 1 0     0 1 c 0    0 1 0 c    0 1 0 0    0 1 0 0
0 1 1 0    0 1 1 0     0 1 1 0     0 1 1 0    0 1 1 0    0 1 1 c    0 1 0 0
0 0 0 0    0 0 0 0     0 0 0 0     0 0 1 0    0 0 1 0    0 0 1 0    0 0 1 c

Example 3

  • N=4
  • M=4
  • A= [[0,0,1,1], [1,0,1,0], [0,1,0,0], [0,0,0,0]]
  • Output = 10

This question maybe the extension of unique paths II problem. Tried to preprocess the grid to convert it into fixed obstacles & then count the paths, but struggling to do so. Is this the right way, is there any better approach?
Thanks in advance.

Comments (2)