Code Implementation

from collections import deque

class Solution:
    def shortestPath(self, grid, k):
        m, n = len(grid), len(grid[0])
        if k >= m + n - 2:
            return m + n - 2
        visited = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
        queue = deque()
        queue.append((0, 0, 0, k))  # row, col, steps, remaining k
        visited[0][0][k] = True

        while queue:
            r, c, steps, rem_k = queue.popleft()
            if r == m - 1 and c == n - 1:
                return steps
            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 = rem_k - grid[nr][nc]
                    if nk >= 0 and not visited[nr][nc][nk]:
                        visited[nr][nc][nk] = True
                        queue.append((nr, nc, steps + 1, nk))
        return -1
      

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        if (k >= m + n - 2) return m + n - 2;
        vector<vector<vector<bool>>> visited(m, vector<vector<bool>>(n, vector<bool>(k+1, false)));
        queue<tuple<int,int,int,int>> q; // row, col, steps, remaining k
        q.emplace(0,0,0,k);
        visited[0][0][k] = true;
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!q.empty()) {
            auto [r,c,steps,rem_k] = q.front(); q.pop();
            if (r == m-1 && c == n-1) return steps;
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int nk = rem_k - grid[nr][nc];
                    if (nk >= 0 && !visited[nr][nc][nk]) {
                        visited[nr][nc][nk] = true;
                        q.emplace(nr, nc, steps+1, nk);
                    }
                }
            }
        }
        return -1;
    }
};
      

import java.util.*;

class Solution {
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        if (k >= m + n - 2) return m + n - 2;
        boolean[][][] visited = new boolean[m][n][k+1];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 0, k}); // row, col, steps, remaining k
        visited[0][0][k] = true;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0], c = curr[1], steps = curr[2], rem_k = curr[3];
            if (r == m-1 && c == n-1) return steps;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    int nk = rem_k - grid[nr][nc];
                    if (nk >= 0 && !visited[nr][nc][nk]) {
                        visited[nr][nc][nk] = true;
                        queue.offer(new int[]{nr, nc, steps+1, nk});
                    }
                }
            }
        }
        return -1;
    }
}
      

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var shortestPath = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    if (k >= m + n - 2) return m + n - 2;
    const visited = Array.from({length: m}, () => Array.from({length: n}, () => Array(k+1).fill(false)));
    const queue = [[0, 0, 0, k]]; // row, col, steps, remaining k
    visited[0][0][k] = true;
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    while (queue.length) {
        const [r, c, steps, rem_k] = queue.shift();
        if (r === m-1 && c === n-1) return steps;
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                const nk = rem_k - grid[nr][nc];
                if (nk >= 0 && !visited[nr][nc][nk]) {
                    visited[nr][nc][nk] = true;
                    queue.push([nr, nc, steps+1, nk]);
                }
            }
        }
    }
    return -1;
};
      

Problem Description

You are given a 2D grid represented as a matrix of integers, where 0 represents an empty cell and 1 represents an obstacle. Your task is to find the shortest path from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1).
You can move up, down, left, or right at each step. Additionally, you are allowed to eliminate up to k obstacles (convert them to empty cells) along your path.
Return the length of the shortest such path, or -1 if it is impossible to reach the target cell.
Key Constraints:

• You may eliminate at most k obstacles.
• You may not move outside the grid.
• Each cell may be visited multiple times, but only if the number of obstacle eliminations used is different.
• There may be multiple possible paths; you must find the shortest.

Thought Process

At first, this problem looks like a classic shortest path search in a grid, commonly solved using Breadth-First Search (BFS). However, the twist is that you are allowed to eliminate up to k obstacles along your path. This means that simply marking a cell as "visited" is not enough, because you may reach the same cell with a different number of eliminations left, leading to different future possibilities.
The brute-force approach would be to try all possible paths, but that is computationally infeasible for larger grids. Instead, we need a way to efficiently keep track of our position, the number of steps taken, and how many obstacles we can still eliminate.
The key insight is to treat each state as a combination of (row, column, remaining eliminations). By using BFS and tracking whether we've visited a particular cell with a specific number of eliminations left, we avoid redundant work and ensure we always find the shortest path.

Solution Approach

We solve this problem using an optimized Breadth-First Search (BFS) algorithm with state tracking. Here's how:

1. State Representation:
   • Each state in our search is represented by four parameters: (row, column, steps, remaining_k), where remaining_k is the number of obstacle eliminations left.
2. Visited Tracking:
   • We use a 3D visited structure: visited[row][col][remaining_k] to ensure we don't revisit the same cell with the same or fewer eliminations left, which would be redundant.
3. BFS Traversal:
   • We use a queue to explore all possible moves from the current cell, in all four directions.
   • If the next cell is an obstacle and we still have eliminations left, we use one elimination and proceed.
   • If the next cell is empty, we move there without using an elimination.
4. Early Exit Optimization:
   • If k is large enough to eliminate all obstacles on the shortest possible path (i.e., k >= m + n - 2), we can return the shortest path length directly, since we can always go straight to the goal.
5. Termination:
   • If we reach the target cell, we return the number of steps taken.
   • If the queue is exhausted without reaching the target, we return -1 (impossible).

Example Walkthrough

Sample Input:
grid = [ [0,1,0,0,0],
[0,1,0,1,0],
[0,0,0,1,0],
[1,1,1,1,0],
[0,0,0,0,0] ]
k = 1

Step-by-Step Trace:

1. We start at (0, 0) with 1 elimination left.
2. From (0, 0), we can only move down to (1, 0) or right to (0, 1). (0, 1) is an obstacle, so if we go there, we use our only elimination.
3. Suppose we go down to (1, 0) first (no elimination used). From there, we can go down to (2, 0), then right to (2, 1), and so on, always choosing empty cells when possible.
4. Eventually, we may need to use our one elimination to bypass an unavoidable obstacle (for instance, to reach (3, 4)).
5. At each step, the BFS ensures we only proceed if we have enough eliminations left for obstacles encountered.
6. When we finally reach (4, 4), if we did so using the fewest steps, BFS guarantees this is the shortest path.

Time and Space Complexity

Brute-force Approach:
The naive brute-force would try all possible paths, leading to exponential time complexity: O(4^{m*n}), which is infeasible for large grids.

Optimized BFS Approach:

• Time Complexity:
  Each cell can be visited at most k+1 times (once for each possible number of eliminations left). There are m * n cells, so the total number of states is O(m * n * k). Each state is processed in constant time, so the overall time complexity is O(m * n * k).
• Space Complexity:
  Similarly, the visited structure and the queue both use O(m * n * k) space in the worst case.

Summary

The "Shortest Path in a Grid with Obstacles Elimination" problem is a variation of the standard shortest path search, enhanced by the ability to eliminate obstacles up to k times. The key insight is to track not just cell positions, but also the number of remaining eliminations, treating each unique combination as a distinct state. By using BFS and a 3D visited structure, we efficiently explore the grid and guarantee the shortest path is found, if one exists. The solution is both elegant and practical, making clever use of BFS's properties and state tracking to handle the obstacle elimination constraint.