Shortest Path in a Grid with Obstacles Elimination solution and explanation

from collections import deque

def shortestPath(grid, k):
    m, n = len(grid), len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    queue = deque([(0, 0, 0, 0)])
    visited = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
    visited[0][0][0] = True
    while queue:
        x, y, steps, remaining_k = queue.popleft()
        if x == m - 1 and y == n - 1:
            return steps
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n:
                new_k = remaining_k + grid[nx][ny]
                if new_k <= k and not visited[nx][ny][new_k]:
                    visited[nx][ny][new_k] = True
                    queue.append((nx, ny, steps + 1, new_k))
    return -1

import java.util.LinkedList;
import java.util.Queue;

public class ShortestPath {
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        boolean[][][] visited = new boolean[m][n][k + 1];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0, 0, 0});
        visited[0][0][0] = true;

        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1], steps = curr[2], obstacles = curr[3];

            if (x == m - 1 && y == n - 1) return steps;

            for (int[] d : directions) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newObstacles = obstacles + grid[nx][ny];
                    if (newObstacles <= k && !visited[nx][ny][newObstacles]) {
                        visited[nx][ny][newObstacles] = true;
                        queue.add(new int[]{nx, ny, steps + 1, newObstacles});
                    }
                }
            }
        }
        return -1;
    }
}

import heapq

def shortestPath(grid, k):
    m, n = len(grid), len(grid[0])
    def heuristic(x, y):
        return (m - 1 - x) + (n - 1 - y)

    pq = [(heuristic(0, 0), 0, 0, 0, 0)]
    visited = [[float('inf')] * n for _ in range(m)]
    visited[0][0] = 0

    while pq:
        _, steps, x, y, obstacles = heapq.heappop(pq)
        if x == m - 1 and y == n - 1:
            return steps

        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n:
                new_obstacles = obstacles + grid[nx][ny]
                if new_obstacles < visited[nx][ny] and new_obstacles <= k:
                    visited[nx][ny] = new_obstacles
                    heapq.heappush(pq, (steps + 1 + heuristic(nx, ny), steps + 1, nx, ny, new_obstacles))
    return -1

using System;
using System.Collections.Generic;

public class GridPath {
    public int ShortestPath(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        int[][] directions = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0} };
        var comparer = Comparer<(int f, int steps, int x, int y, int obstacles)>.Create((a, b) => a.f.CompareTo(b.f));
        SortedSet<(int f, int steps, int x, int y, int obstacles)> pq = new SortedSet<(int, int, int, int, int)>(comparer);
        pq.Add((0 + m - 1 + n - 1, 0, 0, 0, 0));
        int[][] visited = new int[m][];
        for (int i = 0; i < m; ++i) { visited[i] = new int[n]; Array.Fill(visited[i], int.MaxValue); }
        visited[0][0] = 0;

        while (pq.Count > 0) {
            var top = pq.Min;
            pq.Remove(top);
            int steps = top.steps, x = top.x, y = top.y, obstacles = top.obstacles;

            if (x == m - 1 && y == n - 1) return steps;

            foreach (var dir in directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int new_obstacles = obstacles + grid[nx][ny];
                    if (new_obstacles < visited[nx][ny] && new_obstacles <= k) {
                        visited[nx][ny] = new_obstacles;
                        pq.Add((steps + 1 + m - 1 - nx + n - 1 - ny, steps + 1, nx, ny, new_obstacles));
                    }
                }
            }
        }
        return -1;
    }
}

class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        if (k >= m + n - 3) return m + n - 2;
        queue<vector<int>> q;
        q.push({0, 0, k});
        vector<vector<vector<bool>>> vis(m, vector<vector<bool>>(n, vector<bool>(k + 1)));
        vis[0][0][k] = true;
        int ans = 0;
        vector<int> dirs = {-1, 0, 1, 0, -1};
        while (!q.empty()) {
            ++ans;
            for (int i = q.size(); i > 0; --i) {
                auto p = q.front();
                k = p[2];
                q.pop();
                for (int j = 0; j < 4; ++j) {
                    int x = p[0] + dirs[j], y = p[1] + dirs[j + 1];
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        if (x == m - 1 && y == n - 1) return ans;
                        if (grid[x][y] == 0 && !vis[x][y][k]) {
                            q.push({x, y, k});
                            vis[x][y][k] = true;
                        } else if (grid[x][y] == 1 && k > 0 && !vis[x][y][k - 1]) {
                            q.push({x, y, k - 1});
                            vis[x][y][k - 1] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
};

function shortestPath(grid: number[][], k: number): number {
    const m = grid.length;
    const n = grid[0].length;
    if (k >= m + n - 3) {
        return m + n - 2;
    }

    let q: Point[] = [[0, 0, k]];
    const vis = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => Array.from({ length: k + 1 }, () => false)),
    );
    vis[0][0][k] = true;
    const dirs = [0, 1, 0, -1, 0];
    let ans = 0;

    while (q.length) {
        const nextQ: Point[] = [];
        ++ans;

        for (const [i, j, k] of q) {
            for (let d = 0; d < 4; ++d) {
                const [x, y] = [i + dirs[d], j + dirs[d + 1]];
                if (x === m - 1 && y === n - 1) {
                    return ans;
                }
                const v = grid[x]?.[y];
                if (v === 0 && !vis[x][y][k]) {
                    nextQ.push([x, y, k]);
                    vis[x][y][k] = true;
                } else if (v === 1 && k > 0 && !vis[x][y][k - 1]) {
                    nextQ.push([x, y, k - 1]);
                    vis[x][y][k - 1] = true;
                }
            }
        }
        q = nextQ;
    }
    return -1;
}

type Point = [number, number, number];

func shortestPath(grid [][]int, k int) int {
	m, n := len(grid), len(grid[0])
	if k >= m+n-3 {
		return m + n - 2
	}
	q := [][]int{[]int{0, 0, k}}
	vis := make([][][]bool, m)
	for i := range vis {
		vis[i] = make([][]bool, n)
		for j := range vis[i] {
			vis[i][j] = make([]bool, k+1)
		}
	}
	vis[0][0][k] = true
	dirs := []int{-1, 0, 1, 0, -1}
	ans := 0
	for len(q) > 0 {
		ans++
		for i := len(q); i > 0; i-- {
			p := q[0]
			q = q[1:]
			k = p[2]
			for j := 0; j < 4; j++ {
				x, y := p[0]+dirs[j], p[1]+dirs[j+1]
				if x >= 0 && x < m && y >= 0 && y < n {
					if x == m-1 && y == n-1 {
						return ans
					}
					if grid[x][y] == 0 && !vis[x][y][k] {
						q = append(q, []int{x, y, k})
						vis[x][y][k] = true
					} else if grid[x][y] == 1 && k > 0 && !vis[x][y][k-1] {
						q = append(q, []int{x, y, k - 1})
						vis[x][y][k-1] = true
					}
				}
			}
		}
	}
	return -1
}