Shortest Path in a Grid with Obstacle Removal Problem

Shortest Path in a Grid with Obstacle Removal Problem — ExecCode Medium DSA Practice

Solve the Shortest Path in a Grid with Obstacle Removal problem on ExecCode. Free online medium DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

grid is an N by M matrix of 0s and 1s. A 0 is an empty cell and a 1 is an obstacle. Start at the top-left cell (0, 0) and reach the bottom-right cell (N - 1, M - 1). One step moves up, down, left, or right into an adjacent cell. Return the minimum number of steps to reach the destination after removing at most k obstacles. Stepping onto an obstacle removes it and counts once against k. Return -1 when the destination cannot be reached. You are given: grid — N by M matrix of 0s and 1s k — the maximum number of obstacles that may be removed Return the minimum number of steps, or -1 when the destination is unreachable. grid[0][0] and grid[N - 1][M - 1] are empty. A shortest path never needs more than N + M - 2 removals, so use min(k, N + M - 2).

Examples

Input {'grid': [[0, 0, 0], [1, 1, 0], [0, 0, 0], [0, 1, 1], [0, 0, 0]], 'k': 1}; Output 6. Input {'grid': [[0, 1, 1], [1, 1, 1], [1, 1, 0]], 'k': 1}; Output -1. Input {'grid': [[0, 1, 0], [1, 1, 0], [0, 0, 0]], 'k': 2}; Output 4

Constraints

1 <= grid.length, grid[0].length <= 400 0 <= k <= grid.length grid[0].length grid[i][j] is 0 or 1 grid[0][0] == grid[N - 1][M - 1] == 0 Expected time: O(N M * K)

Practice Shortest Path in a Grid with Obstacle Removal free on ExecCode. Browse DSA problems, topic map, and placement guides.