1293. Shortest Path in a Grid with Obstacles Elimination LeetCode Solution
In this guide, you will get 1293. Shortest Path in a Grid with Obstacles Elimination LeetCode Solution with the best time and space complexity. The solution to Shortest Path in a Grid with Obstacles Elimination problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Shortest Path in a Grid with Obstacles Elimination
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.
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
Complexity Analysis
Time Complexity: O(mnk)
Space Complexity: O(mnk)
1293. Shortest Path in a Grid with Obstacles Elimination LeetCode Solution in C++
class Solution {
public:
int shortestPath(vector<vector<int>>& grid, int k) {
const int m = grid.size();
const int n = grid[0].size();
if (m == 1 && n == 1)
return 0;
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
queue<tuple<int, int, int>> q{{{0, 0, k}}}; // (i, j, eliminate)
vector<vector<vector<bool>>> seen(
m, vector<vector<bool>>(n, vector<bool>(k + 1)));
seen[0][0][k] = true;
for (int step = 1; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
const auto [i, j, eliminate] = q.front();
q.pop();
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (x == m - 1 && y == n - 1)
return step;
if (grid[x][y] == 1 && eliminate == 0)
continue;
const int newEliminate = eliminate - grid[x][y];
if (seen[x][y][newEliminate])
continue;
q.emplace(x, y, newEliminate);
seen[x][y][newEliminate] = true;
}
}
return -1;
}
}; /* code provided by PROGIEZ */
1293. Shortest Path in a Grid with Obstacles Elimination LeetCode Solution in Java
class Solution {
public int shortestPath(int[][] grid, int k) {
record T(int i, int j, int eliminate) {}
final int m = grid.length;
final int n = grid[0].length;
if (m == 1 && n == 1)
return 0;
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
Queue<T> q = new ArrayDeque<>(List.of(new T(0, 0, k)));
boolean[][][] seen = new boolean[m][n][k + 1];
seen[0][0][k] = true;
for (int step = 1; !q.isEmpty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
final int i = q.peek().i;
final int j = q.peek().j;
final int eliminate = q.poll().eliminate;
for (int l = 0; l < 4; ++l) {
final int x = i + dirs[l][0];
final int y = j + dirs[l][1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (x == m - 1 && y == n - 1)
return step;
if (grid[x][y] == 1 && eliminate == 0)
continue;
final int newEliminate = eliminate - grid[x][y];
if (seen[x][y][newEliminate])
continue;
q.offer(new T(x, y, newEliminate));
seen[x][y][newEliminate] = true;
}
}
return -1;
}
} // code provided by PROGIEZ
1293. Shortest Path in a Grid with Obstacles Elimination LeetCode Solution in Python
class Solution:
def shortestPath(self, grid: list[list[int]], k: int) -> int:
m = len(grid)
n = len(grid[0])
if m == 1 and n == 1:
return 0
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
q = collections.deque([(0, 0, k)])
seen = {(0, 0, k)}
step = 0
while q:
step += 1
for _ in range(len(q)):
i, j, eliminate = q.popleft()
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == m or y < 0 or y == n:
continue
if x == m - 1 and y == n - 1:
return step
if grid[x][y] == 1 and eliminate == 0:
continue
newEliminate = eliminate - grid[x][y]
if (x, y, newEliminate) in seen:
continue
q.append((x, y, newEliminate))
seen.add((x, y, newEliminate))
return -1 # code by PROGIEZ
