Shortest Path in a Grid with Obstacles Elimination

hard bfs grid

Problem

Given an m × n grid where cells are 0 (empty) or 1 (obstacle), and an integer k, return the minimum number of steps to walk from (0,0) to (m-1, n-1) (4-directional), eliminating at most k obstacles. Return -1 if impossible.

Inputgrid = [[0,1,1],[0,0,0]], k = 1

Output3

Best path goes (0,0) → (1,0) → (1,1) → (1,2). 3 moves, no eliminations needed.

grid (JSON of 0/1)

from collections import deque

def shortest_path(grid, k):
    m, n = len(grid), len(grid[0])
    if m == 1 and n == 1: return 0
    best = [[-1] * n for _ in range(m)]
    best[0][0] = k
    q = deque([(0, 0, k, 0)])
    while q:
        r, c, kk, d = q.popleft()
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                nk = kk - grid[nr][nc]
                if nk < 0 or nk <= best[nr][nc]: continue
                if (nr, nc) == (m-1, n-1): return d + 1
                best[nr][nc] = nk
                q.append((nr, nc, nk, d + 1))
    return -1

function shortestPath(grid, k) {
  const m = grid.length, n = grid[0].length;
  if (m === 1 && n === 1) return 0;
  const best = Array.from({ length: m }, () => new Array(n).fill(-1));
  best[0][0] = k;
  const q = [[0, 0, k, 0]];
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (q.length) {
    const [r, c, kk, d] = q.shift();
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
      const nk = kk - grid[nr][nc];
      if (nk < 0 || nk <= best[nr][nc]) continue;
      if (nr === m - 1 && nc === n - 1) return d + 1;
      best[nr][nc] = nk;
      q.push([nr, nc, nk, d + 1]);
    }
  }
  return -1;
}

class Solution {
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        if (m == 1 && n == 1) return 0;
        int[][] best = new int[m][n];
        for (int[] row : best) Arrays.fill(row, -1);
        best[0][0] = k;
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0, k, 0});
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                int nk = cur[2] - grid[nr][nc];
                if (nk < 0 || nk <= best[nr][nc]) continue;
                if (nr == m - 1 && nc == n - 1) return cur[3] + 1;
                best[nr][nc] = nk;
                q.offer(new int[]{nr, nc, nk, cur[3] + 1});
            }
        }
        return -1;
    }
}

int shortestPath(vector<vector<int>>& grid, int k) {
    int m = grid.size(), n = grid[0].size();
    if (m == 1 && n == 1) return 0;
    vector<vector<int>> best(m, vector<int>(n, -1));
    best[0][0] = k;
    queue<array<int, 4>> q;
    q.push({0, 0, k, 0});
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.empty()) {
        auto [r, c, kk, d] = q.front(); q.pop();
        for (auto& dd : dirs) {
            int nr = r + dd[0], nc = c + dd[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            int nk = kk - grid[nr][nc];
            if (nk < 0 || nk <= best[nr][nc]) continue;
            if (nr == m - 1 && nc == n - 1) return d + 1;
            best[nr][nc] = nk;
            q.push({nr, nc, nk, d + 1});
        }
    }
    return -1;
}

Explanation

This is a shortest-path problem, so BFS gives the fewest steps. The twist is that we can smash up to k obstacles, so where you stand isn't the full story — how many eliminations you have left matters too. The BFS state is therefore (row, col, remaining k).

The clever part is the pruning array best[r][c]: it stores the most remaining eliminations we've ever had when arriving at that cell. If we reach a cell with the same or fewer eliminations than before, that path is no better, so we skip it. Keeping more k is always at least as good.

From each cell we try the four neighbors. Stepping onto an obstacle costs one elimination: nk = kk - grid[nr][nc]. If nk < 0 we can't afford it, and if nk doesn't beat best[nr][nc] we prune. Otherwise we record it and enqueue it with distance d + 1.

Example: grid = [[0,1,1],[0,0,0]], k = 1. BFS finds the route (0,0) → (1,0) → (1,1) → (1,2), which avoids obstacles entirely — 3 moves with the elimination unused.

Because BFS explores by increasing distance, the first time we pop the bottom-right corner we've found the shortest valid path; if the queue empties first, it's unreachable and we return -1.

Time: O(m · n · k) Space: O(m · n)