Shortest Path in a Grid with Obstacles Elimination

Leetcode Problem 1293: Shortest Path in a Grid with Obstacles Elimination

Problem Summary

You are given an m × n grid where 0 is a free cell and 1 is an obstacle. You start at (0, 0) and want to reach (m-1, n-1). In one step you can move to any of the 4 adjacent free cells. You can eliminate at most k obstacles. Return the minimum number of steps to reach the destination, or -1 if it is impossible.

Constraints:

• The grid has between 1 and 40 rows and 1 and 40 columns.
• Each cell is 0 (free) or 1 (obstacle).
• k is a non-negative integer up to m × n.

Techniques

• Array
• Breadth-First Search
• Matrix

Solution

function shortestPath(grid: number[][], k: number): number {
    const rows = grid.length;
    const cols = grid[0].length;
    const visited = Array.from(
        { length: rows },
        () => Array(cols).fill(-1)
    );

    const queue: [number, number, number][] = [[0, 0, k]];
    visited[0][0] = k;

    let steps = 0;

    const dirs = [
        [1, 0],
        [-1, 0],
        [0, 1],
        [0, -1]
    ];

    while (queue.length > 0) {
        let levelSize = queue.length;

        while (levelSize-- > 0) {
            const [row, col, kLeft] = queue.shift()!;

            if (row === rows - 1 && col === cols - 1) {
                return steps;
            }

            for (const [dr, dc] of dirs) {
                const newRow = row + dr;
                const newColumn = col + dc;

                if (newRow < 0 || newColumn < 0 || newRow >= rows || newColumn >= cols) { 
                    continue;
                }

                const newK = kLeft - grid[newRow][newColumn];

                if (newK >= 0 && newK > visited[newRow][newColumn]) {
                    visited[newRow][newColumn] = newK;
                    queue.push([newRow, newColumn, newK]);
                }
            }
        }

        steps++;
    }

    return -1;
}

console.log(shortestPath([[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], 1)); // Output: 6