How should I practice Grid Paths with Override Passes?

Start by reading the full statement, solve the visible examples, then compare the pattern against related IMC online assessment problems in FastPrep.

Is Grid Paths with Override Passes associated with IMC?

FastPrep tags this as a IMC online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Grid Paths with Override Passes

Learn this problem

● MediumIMIMCINTERNNEW GRADOA

Problem statement

A delivery robot navigates a city represented by an n x m grid. A cell containing 1 is an open street, while a cell containing 0 is blocked by construction.

The robot starts at the top-left cell (0, 0) and must reach the bottom-right cell (n - 1, m - 1). The starting and ending cells may themselves be blocked. From any cell, the robot may move exactly one cell Right or one cell Down.

The robot has k override passes. Including one blocked cell in a path consumes exactly one pass, and the robot may consume at most k passes over its entire path.

Return the number of distinct paths from the start to the destination that use at most k override passes, modulo 10^9 + 7.

Function

numPaths(grid: int[][], k: int) → int

Examples

Example 1

grid = [[1,0,1],[1,0,1],[1,1,1]]k = 1return = 4

Four paths use at most one override pass. Three of them enter exactly one blocked cell, and the path that moves Down, Down, Right, Right enters no blocked cells.

Example 2

grid = [[1,0],[0,1]]k = 0return = 0

Both possible first moves enter a blocked cell, but no override pass is available.

Constraints

1 <= n, m <= 200
0 <= k <= 10
Every cell of grid is either 0 or 1.