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 Bloomberg phone screen problems in FastPrep.

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

FastPrep tags this as a Bloomberg 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

BloombergFULLTIMEPHONE 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. Start at (0, 0) and move one cell up, down, left, or right.

Return the minimum number of moves needed to reach (m - 1, n - 1) when you may eliminate at most k obstacles. Return -1 when the destination is unreachable.

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

A shortest route has six moves and eliminates one obstacle.

Example 2

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

Every route to the destination crosses more than one obstacle.

Constraints

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