DSA problem
Shortest Path in a Grid with Obstacles Elimination
You are given an m x n grid where each cell is either 0 (empty) or 1 (obstacle). You start at cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1). You may move 4-directionally to an adjacent empty cell. Additionally you have a quota: you may eliminate up to k obstacles along the way, walking through them as if they were empty cells. Return the minimum number of steps to reach the bottom-right corner, or -1 if it is impossible.
If k were always 0, this would be a plain BFS on a grid. The twist is that the state of "being at cell (r, c) with x eliminations remaining" is genuinely different from "being at (r, c) with y eliminations remaining" — the available futures depend on how many eliminations you still have.
Therefore the correct state space is the triple (r, c, k_left), where k_left is the number of obstacle eliminations still available. BFS over this expanded graph guarantees the shortest path. There are at most m * n * (k + 1) such states, so the algorithm is polynomial.
To prevent revisiting useless states, mark (r, c, k_left) as visited when enqueued. A common optimisation: if k >= m + n - 2 you can always walk diagonally through everything, so the answer is m + n - 2. This early-return short-circuits enormous k values. Otherwise BFS runs in O(m * n * k) time and space.
Examples
grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 16grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1-1grid = [[0,0],[0,0]], k = 02Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 40
- 1 <= k <= m * n
- grid[i][j] is either 0 or 1.
- grid[0][0] == grid[m - 1][n - 1] == 0
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.