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.

Examples

Example 1:

1
2
3
4
5
6
7


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:

1
2
3
4
5


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

Solution

Method 1 – BFS with State Tracking

Intuition

We need to find the shortest path from the top-left to the bottom-right of a grid, where we can eliminate up to k obstacles. This is a classic BFS problem, but we must track not only the position but also how many obstacles we have eliminated so far.

Approach

Use BFS to explore the grid from the start position.
For each cell, track the minimum number of obstacles eliminated to reach it.
Use a queue to store the current position, steps taken, and obstacles eliminated.
For each move, if the next cell is an obstacle and we have eliminations left, proceed and increment the elimination count.
If the next cell is not an obstacle, proceed as usual.
Use a 3D visited array or a map to avoid revisiting states with more eliminations.
Return the number of steps when reaching the bottom-right cell; if not possible, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
public:
    int shortestPath(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> vis(m, vector<int>(n, -1));
        queue<tuple<int, int, int>> q;
        q.push({0, 0, 0});
        vis[0][0] = 0;
        int steps = 0;
        int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                auto [x, y, obs] = q.front(); q.pop();
                if (x == m-1 && y == n-1) return steps;
                for (auto& d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        int nobs = obs + grid[nx][ny];
                        if (nobs <= k && (vis[nx][ny] == -1 || nobs < vis[nx][ny])) {
                            vis[nx][ny] = nobs;
                            q.push({nx, ny, nobs});
                        }
                    }
                }
            }
            steps++;
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


func shortestPath(grid [][]int, k int) int {
    m, n := len(grid), len(grid[0])
    vis := make([][]int, m)
    for i := range vis {
        vis[i] = make([]int, n)
        for j := range vis[i] {
            vis[i][j] = -1
        }
    }
    type node struct{ x, y, obs int }
    q := []node{{0, 0, 0}}
    vis[0][0] = 0
    steps := 0
    dirs := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
    for len(q) > 0 {
        sz := len(q)
        for i := 0; i < sz; i++ {
            cur := q[0]; q = q[1:]
            if cur.x == m-1 && cur.y == n-1 {
                return steps
            }
            for _, d := range dirs {
                nx, ny := cur.x+d[0], cur.y+d[1]
                if nx >= 0 && nx < m && ny >= 0 && ny < n {
                    nobs := cur.obs + grid[nx][ny]
                    if nobs <= k && (vis[nx][ny] == -1 || nobs < vis[nx][ny]) {
                        vis[nx][ny] = nobs
                        q = append(q, node{nx, ny, nobs})
                    }
                }
            }
        }
        steps++
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        int[][] vis = new int[m][n];
        for (int[] row : vis) Arrays.fill(row, -1);
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0, 0});
        vis[0][0] = 0;
        int steps = 0;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int[] cur = q.poll();
                int x = cur[0], y = cur[1], obs = cur[2];
                if (x == m-1 && y == n-1) return steps;
                for (int[] d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        int nobs = obs + grid[nx][ny];
                        if (nobs <= k && (vis[nx][ny] == -1 || nobs < vis[nx][ny])) {
                            vis[nx][ny] = nobs;
                            q.offer(new int[]{nx, ny, nobs});
                        }
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
    fun shortestPath(grid: Array<IntArray>, k: Int): Int {
        val m = grid.size
        val n = grid[0].size
        val vis = Array(m) { IntArray(n) { -1 } }
        val q = ArrayDeque<Triple<Int, Int, Int>>()
        q.add(Triple(0, 0, 0))
        vis[0][0] = 0
        var steps = 0
        val dirs = arrayOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)
        while (q.isNotEmpty()) {
            repeat(q.size) {
                val (x, y, obs) = q.removeFirst()
                if (x == m-1 && y == n-1) return steps
                for ((dx, dy) in dirs) {
                    val nx = x + dx
                    val ny = y + dy
                    if (nx in 0 until m && ny in 0 until n) {
                        val nobs = obs + grid[nx][ny]
                        if (nobs <= k && (vis[nx][ny] == -1 || nobs < vis[nx][ny])) {
                            vis[nx][ny] = nobs
                            q.add(Triple(nx, ny, nobs))
                        }
                    }
                }
            }
            steps++
        }
        return -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def shortestPath(self, grid: list[list[int]], k: int) -> int:
        from collections import deque
        m, n = len(grid), len(grid[0])
        vis = [[-1]*n for _ in range(m)]
        q = deque([(0, 0, 0)])
        vis[0][0] = 0
        steps = 0
        dirs = [(0,1),(1,0),(0,-1),(-1,0)]
        while q:
            for _ in range(len(q)):
                x, y, obs = q.popleft()
                if x == m-1 and y == n-1:
                    return steps
                for dx, dy in dirs:
                    nx, ny = x+dx, y+dy
                    if 0 <= nx < m and 0 <= ny < n:
                        nobs = obs + grid[nx][ny]
                        if nobs <= k and (vis[nx][ny] == -1 or nobs < vis[nx][ny]):
                            vis[nx][ny] = nobs
                            q.append((nx, ny, nobs))
            steps += 1
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


use std::collections::VecDeque;
impl Solution {
    pub fn shortest_path(grid: Vec<Vec<i32>>, k: i32) -> i32 {
        let (m, n) = (grid.len(), grid[0].len());
        let mut vis = vec![vec![-1; n]; m];
        let mut q = VecDeque::new();
        q.push_back((0, 0, 0));
        vis[0][0] = 0;
        let mut steps = 0;
        let dirs = [(0,1),(1,0),(0,-1),(-1,0)];
        while !q.is_empty() {
            for _ in 0..q.len() {
                let (x, y, obs) = q.pop_front().unwrap();
                if x == m-1 && y == n-1 {
                    return steps as i32;
                }
                for (dx, dy) in dirs.iter() {
                    let (nx, ny) = (x as i32 + dx, y as i32 + dy);
                    if nx >= 0 && nx < m as i32 && ny >= 0 && ny < n as i32 {
                        let (nx, ny) = (nx as usize, ny as usize);
                        let nobs = obs + grid[nx][ny];
                        if nobs <= k && (vis[nx][ny] == -1 || nobs < vis[nx][ny]) {
                            vis[nx][ny] = nobs;
                            q.push_back((nx, ny, nobs));
                        }
                    }
                }
            }
            steps += 1;
        }
        -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution {
    shortestPath(grid: number[][], k: number): number {
        const m = grid.length, n = grid[0].length;
        const vis = Array.from({length: m}, () => Array(n).fill(-1));
        const q: [number, number, number][] = [[0, 0, 0]];
        vis[0][0] = 0;
        let steps = 0;
        const dirs = [[0,1],[1,0],[0,-1],[-1,0]];
        while (q.length) {
            const sz = q.length;
            for (let i = 0; i < sz; i++) {
                const [x, y, obs] = q.shift()!;
                if (x === m-1 && y === n-1) return steps;
                for (const [dx, dy] of dirs) {
                    const nx = x + dx, ny = y + dy;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        const nobs = obs + grid[nx][ny];
                        if (nobs <= k && (vis[nx][ny] === -1 || nobs < vis[nx][ny])) {
                            vis[nx][ny] = nobs;
                            q.push([nx, ny, nobs]);
                        }
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}

Complexity

⏰ Time complexity: O(m * n * k), since each cell can be visited with up to k different elimination counts.
🧺 Space complexity: O(m * n * k), for the visited states and queue.

published: true

Problem#

Examples#

Solution#

Method 1 – BFS with State Tracking#

Intuition#

Approach#

Code#

Complexity#