Shortest Path in a Grid with Obstacles Elimination — Hard Problem & Solution

Problem statement

grid is an m x n matrix where 0 is an empty cell and 1 is an obstacle. In one step you move up, down, left or right to an adjacent cell.

You start in the top-left corner (0, 0) and want to reach the bottom-right corner (m - 1, n - 1). Along the way you may eliminate at most k obstacles, which lets you step onto those obstacle cells.

Return the minimum number of steps needed, or -1 if the corner cannot be reached with at most k eliminations.

Example 1

Input: grid = [[0,1,1],[1,1,0],[1,0,0]], k = 1
Output: -1
Explanation: Every route from the start crosses at least two obstacles.

Example 2

Input: grid = [[0,1,1],[1,1,0],[1,0,0]], k = 2
Output: 4
Explanation: Right through an obstacle, down through another, then down and right.

Example 3

Input: grid = [[0,0,0,0],[1,1,1,0],[0,0,0,0],[0,1,1,1],[0,0,0,0]], k = 1
Output: 7
Explanation: Without eliminations the path snakes for 13 steps; removing the obstacle at `(1,0)` allows the direct 7-step route.

Constraints

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

How to solve Shortest Path in a Grid with Obstacles Elimination

Augment the BFS state with the number of eliminations remaining; every edge still costs one step, so BFS on the augmented graph is still a shortest-path search.

Approach

1. If k >= m + n - 2, return m + n - 2 — a monotone path has at most m + n - 3 interior cells to clear.
2. BFS from (0, 0, k) with visited[r][c][rem].
3. From (r, c, rem) try the four neighbours; entering an obstacle needs rem > 0 and leads to rem - 1, an empty cell keeps rem.
4. Return the BFS layer at which (m - 1, n - 1) is first dequeued (with any rem), or -1.

Why it works

Each state captures everything that affects the future: the position and how many obstacles can still be removed. Every move costs exactly one step, so BFS over these states reaches each one at its minimum distance, and the first time the target cell appears is the shortest path that respects the elimination budget.

Complexity

• Time — O(m · n · k)
• Space — O(m · n · k)

Pitfalls

• Marking a cell visited regardless of rem is wrong: reaching it later with more eliminations left can still lead to a shorter overall path.
• Without the Manhattan shortcut, a large k makes the state space m · n · k, which is needlessly large.
• A 1 × 1 grid needs 0 steps.

Reference solution

Python

from typing import List
from collections import deque

def shortestPath(grid: List[List[int]], k: int) -> int:
    m, n = len(grid), len(grid[0])
    if k >= m + n - 2:
        return m + n - 2
    seen = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
    seen[0][0][k] = True
    q = deque([(0, 0, k)])
    steps = 0
    while q:
        for _ in range(len(q)):
            r, c, rem = q.popleft()
            if r == m - 1 and c == n - 1:
                return steps
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                a, b = r + dr, c + dc
                if 0 <= a < m and 0 <= b < n:
                    left = rem - grid[a][b]
                    if left >= 0 and not seen[a][b][left]:
                        seen[a][b][left] = True
                        q.append((a, b, left))
        steps += 1
    return -1

JavaScript

var shortestPath = function(grid, k) {
    var m = grid.length, n = grid[0].length;
    if (k >= m + n - 2) return m + n - 2;
    var K = k + 1;
    var seen = new Array(m * n * K).fill(false);
    var cur = [[0, 0, k]];
    seen[k] = true;
    var dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    for (var steps = 0; cur.length > 0; steps++) {
        var next = [];
        for (var i = 0; i < cur.length; i++) {
            var r = cur[i][0], c = cur[i][1], rem = cur[i][2];
            if (r === m - 1 && c === n - 1) return steps;
            for (var d = 0; d < 4; d++) {
                var a = r + dirs[d][0], b = c + dirs[d][1];
                if (a < 0 || b < 0 || a >= m || b >= n) continue;
                var left = rem - grid[a][b];
                if (left < 0) continue;
                var key = (a * n + b) * K + left;
                if (!seen[key]) { seen[key] = true; next.push([a, b, left]); }
            }
        }
        cur = next;
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Remove Boxes Hard
• Number of Squareful Arrays Hard
• Closest Subsequence Sum Hard
• Maximum Number of Achievable Transfer Requests Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard