Shortest Path in a Grid with Obstacles Elimination

Shortest Path in a Grid with Obstacles Elimination - Problem

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.

Input & Output

Example 1 — Basic Elimination

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

› Output: 6

💡 Note: Shortest path: (0,0) → (1,0) eliminate → (2,0) eliminate → (2,1) → (2,2) in 6 steps, but actually optimal is (0,0) → (1,0) → (2,1) → (2,2) eliminating 2 obstacles

Example 2 — No Elimination Needed

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

› Output: 6

💡 Note: Path around obstacles: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (2,2) in 4 steps

Example 3 — Impossible Case

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

› Output: -1

💡 Note: Need to eliminate at least 6 obstacles to reach destination, but k=1 is insufficient

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

Visualization

Tap to expand

Understanding the Visualization

Input

Grid with obstacles (1) and empty cells (0), plus k eliminations allowed

Process

Use BFS to explore states (row, col, eliminations_left)

Output

Minimum steps to reach destination, or -1 if impossible

Key Takeaway

🎯 Key Insight: Model the problem as 3D state space where each state represents position and remaining eliminations

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to model each position as a 3D state (row, col, eliminations_remaining) and use BFS to find the shortest path. The optimal approach is BFS with state tracking, achieving Time: O(m×n×k), Space: O(m×n×k).

Common Approaches

Approach	Time	Space	Notes
✓ BFS with 3D State	O(m×n×k)	O(m×n×k)	Use BFS with state (row, col, eliminations_left) for shortest path
DFS with Backtracking	O(4^(m×n))	O(m×n)	Try all possible paths using depth-first search

BFS with 3D State — Algorithm Steps

Start BFS from (0,0,k) state
For each state, try all 4 directions
Track visited states to avoid cycles
Return steps when destination is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with state (0,0,k) in queue

Expand

For each state, try all 4 directions with updated eliminations

Found

First time we reach destination gives minimum steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_QUEUE 100000
#define MAX_STATES 100000

typedef struct {
    int row, col, eliminations, steps;
} State;

typedef struct {
    State queue[MAX_QUEUE];
    int front, rear;
} Queue;

typedef struct {
    char states[MAX_STATES][20];
    int count;
} VisitedSet;

int contains(VisitedSet* set, char* state) {
    for (int i = 0; i < set->count; i++) {
        if (strcmp(set->states[i], state) == 0) {
            return 1;
        }
    }
    return 0;
}

void add(VisitedSet* set, char* state) {
    if (set->count < MAX_STATES) {
        strcpy(set->states[set->count], state);
        set->count++;
    }
}

void enqueue(Queue* q, State state) {
    q->queue[q->rear] = state;
    q->rear = (q->rear + 1) % MAX_QUEUE;
}

State dequeue(Queue* q) {
    State state = q->queue[q->front];
    q->front = (q->front + 1) % MAX_QUEUE;
    return state;
}

int isEmpty(Queue* q) {
    return q->front == q->rear;
}

int solution(int** grid, int gridSize, int* gridColSize, int k) {
    if (gridSize == 0 || gridColSize[0] == 0) {
        return -1;
    }
    
    int m = gridSize, n = gridColSize[0];
    if (m == 1 && n == 1) {
        return 0;
    }
    
    // If we can eliminate enough obstacles to go straight
    if (k >= m + n - 3) {
        return m + n - 2;
    }
    
    Queue q = {.front = 0, .rear = 0};
    VisitedSet visited = {.count = 0};
    
    State start = {0, 0, k, 0};
    enqueue(&q, start);
    
    char initialState[20];
    sprintf(initialState, "0,0,%d", k);
    add(&visited, initialState);
    
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    while (!isEmpty(&q)) {
        State curr = dequeue(&q);
        
        for (int i = 0; i < 4; i++) {
            int newRow = curr.row + directions[i][0];
            int newCol = curr.col + directions[i][1];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                int newEliminations = curr.eliminations - grid[newRow][newCol];
                char state[20];
                sprintf(state, "%d,%d,%d", newRow, newCol, newEliminations);
                
                if (newEliminations >= 0 && !contains(&visited, state)) {
                    if (newRow == m - 1 && newCol == n - 1) {
                        return curr.steps + 1;
                    }
                    
                    add(&visited, state);
                    State newState = {newRow, newCol, newEliminations, curr.steps + 1};
                    enqueue(&q, newState);
                }
            }
        }
    }
    
    return -1;
}

int main() {
    // Simple test case
    int grid[3][3] = {{0,1,1},{1,1,1},{1,0,0}};
    int* gridPtr[3] = {grid[0], grid[1], grid[2]};
    int gridColSize[3] = {3, 3, 3};
    int k = 1;
    
    printf("%d\n", solution(gridPtr, 3, gridColSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×k)

Each cell can be visited at most k+1 times with different elimination counts

✓ Linear Growth

Space Complexity

O(m×n×k)

Queue and visited set store up to m×n×k states

⚡ Linearithmic Space

34.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS with 3D State — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler