1293. Shortest Path in a Grid with Obstacles Elimination

Shortest Path in a Grid with Obstacles Elimination

Problem Description

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

 

Example 1:

Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1
Output: 6

Explanation: 
The shortest path without eliminating any obstacle is 10.
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

Example 2:

Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1
Output: -1

Explanation: We need to eliminate at least two obstacles to find such a walk.

 

Constraints:

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

Approach) Breadth-First Search (BFS)

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var shortestPath = function(grid, k) {
    /**
        Concept:
        -- Since we are given a grid of cells and we have to find the shortest path between two cells,
           we can solve this problem using BFS.
        -- The grid may contain many obstacles and there are K obstacles that can be eliminated.
        -- Once we have eliminated K obstacles, there's no path and an alternate path must be considered
        -- Therefore, we must know at each cell we are visiting what value of K we brought to that cell
        -- Also, to avoid getting stuck in a loop of wrong path, we must avoid paths already visited
        
        Approach:
        -- Push a tuple [ row, col, remainingK ] into a queue. Also put combination as seen in a set.
        -- For each tuple that we remove from the queue:
           -- Check if row and col are lower right coordinates. If true, return moves taken so far.
           -- If not true,
              -- Move in each of the four directions from that cell to find its neighbor
              -- Validate the neighbor:
                 -- Check for out of bounds
                 -- Check if neighbor cell has an obstacle and if K is exhausted
              -- If validated, do the following if neighbor is not seen before:
                 -- If not obstacle, add neighbor coordinates and remaining K to queue and set.
                 -- If obstacle, decrement remaining k and add values to queue and set.
    */
    
    // Time Complexity: O(m*n) --> Worst case traversing all cells
    // Space Complexity: O(m*n) --> Worst case storing all cells
    
    if (!grid || grid.length === 0) return 0;
    
    const rows = grid.length, cols = grid[0].length;
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const visited = new Set();
    visited.add(`0-0-${k}`);
    
    let moves = 0, queue = [[0, 0, k]];// Starting coordinates and k
    
    while (queue.length > 0) {
        let nextMoves = [];
        
        while (queue.length > 0) {
            let [x, y, remainingK] = queue.pop();
            
            if (x === rows - 1 && y === cols - 1) return moves;// Reached destination => return moves
            
            for (const direction of directions) {
                let row = x + direction[0], col = y + direction[1];
                
                // Check for out of bounds or too many obstacles to eliminate
                if (row < 0 || col < 0 || row >= rows || col >= cols ||
                   (grid[row][col] === 1 && remainingK === 0)) continue;
                
                // Consider a decremented k while discovering next 4 neighbors if obstacle
                let newK = grid[row][col] === 1 ? remainingK - 1 : remainingK;
                let key = `${row}-${col}-${newK}`;
                
                if (!visited.has(key)) {
                    visited.add(key);
                    nextMoves.push([row, col, newK]);
                }
            }
        }
        
        queue = nextMoves;
        moves++;
    }
    
    return -1;// return -1 if no path found
};

Approach) A* 

var shortestPath = function(grid, k) {
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    const rows = grid.length, cols = grid[0].length;
    const visited = new Set([`0,0,0`]);
    const manDist = (r, c) => (rows - 1 - r) + (cols - 1 - c);

    // Priority queue element format: [priority, r, c, remaining eliminations, steps so far]
    const queue = new MinPriorityQueue({priority: el => el[0]});
    queue.enqueue([manDist(0, 0), 0, 0, k, 0]); 
    
    while (queue.size()) {
        const [estimate, r, c, elim, steps] = queue.dequeue().element;
        
        // Early return if Manhattan Distance is less than / equal to available eliminations
        let remainMinDist = estimate - steps ** 0.5;
        if (remainMinDist <= elim) return estimate;
    
        // Reached bottom right cell
        if (r == rows - 1 && c == cols - 1) return steps;
        
        // Add four adjacent cells to queue
        dirs.forEach((el) => {
            let newR = r + el[0], newC = c + el[1];
            if (newR >= 0 && newC >= 0 && newR < rows && newC < cols) {
                let newElim = elim - grid[newR][newC];
                let newKey = `${newR},${newC},${newElim}`;
                if (newElim >= 0 && !visited.has(newKey)) {
                    let newEstim = manDist(newR, newC) + (steps + 1) ** 2;
                    visited.add(newKey);
                    queue.enqueue([newEstim, newR, newC, newElim, steps + 1]);
                }
            }
        })
    }
    return -1;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1293. Shortest Path in a Grid with Obstacles Elimination

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!