How should I practice Shortest Path in a Grid with Obstacles Elimination?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Mercor phone screen problems in FastPrep.

Is Shortest Path in a Grid with Obstacles Elimination associated with Mercor?

FastPrep tags this as a Mercor phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Matrix

Shortest Path in a Grid with Obstacles Elimination

Learn this problem

● Hard

MercorFULLTIMEPHONE SCREEN

Problem statement

You are given an m x n binary grid. A value of 0 is an empty cell and a value of 1 is an obstacle. Starting at the top-left cell, you may move one step up, down, left, or right.

You may eliminate at most k obstacles. Return the minimum number of steps needed to reach the bottom-right cell, or -1 when it is impossible.

Function

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

Examples

Example 1

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

Eliminating one obstacle allows a shortest route of six steps.

Example 2

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

Every route to the destination requires eliminating more than one obstacle.

Constraints

1 <= m, n <= 40
1 <= m * n
grid[i][j] is either 0 or 1.
grid[0][0] == 0 and grid[m - 1][n - 1] == 0.
0 <= k <= m * n