Shortest Path in a Grid with Obstacles Elimination — LeetCode 1293 Python Solution
HardBreadth-First SearchArrayMatrix
- Problem
- #1293
- Pattern
- Matrix and Grid
- Reading time
- 4 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
Python
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
if k >= m + n - 3:
return m + n - 2
q = deque([(0, 0, k)])
vis = {(0, 0, k)}
ans = 0
while q:
ans += 1
for _ in range(len(q)):
i, j, k = q.popleft()
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if x == m - 1 and y == n - 1:
return ans
if grid[x][y] == 0 and (x, y, k) not in vis:
q.append((x, y, k))
vis.add((x, y, k))
if grid[x][y] == 1 and k > 0 and (x, y, k - 1) not in vis:
q.append((x, y, k - 1))
vis.add((x, y, k - 1))
return -1Complexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination?
- LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination cover?
- LeetCode 1293. Shortest Path in a Grid with Obstacles Elimination is tagged Breadth-First Search, Array and Matrix on LeetCode.