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.lengthn == grid[i].length1 <= m, n <= 401 <= k <= m * ngrid[i][j] is either 0 or 1.grid[0][0] == grid[m - 1][n - 1] == 0This approach utilizes Breadth-First Search (BFS) to explore paths in the grid, while maintaining a state that includes the current position and number of obstacles removed. We can advance through the grid using BFS, and track paths using a queue where each entry consists of a tuple containing the current position, number of steps taken, and the number of obstacles removed. A three-dimensional list keeps track of states visited at any position with a particular obstacle count to avoid unnecessary reprocessing.
In the Python solution, we initiate a queue to perform BFS and a visited array to track visited states. Each state contains the (x, y) position, number of steps taken, and the number of obstacles removed. For each state, we try moving in four directions and push valid states into the queue.
Java
The time complexity is O(m * n * k) because we process each cell at most k times (once for each possible count of removed obstacles). The space complexity is also O(m * n * k) due to the visited array used for tracking states.
A* Search is an informed search algorithm, which is often used in pathfinding and graph traversal. For this grid problem, we use a priority queue to explore paths, using a heuristic function. The heuristic can be the Manhattan distance to the target minus the remaining k value, incentivizing routes closer to the target with lesser obstacle removals.
Leveraging a priority queue for A* search, this Python solution uses a heuristic to decide which paths to explore first. We prioritize paths by their distance to the target, pushing the states into the queue with both the actual cost (steps traveled) and the estimated cost (heuristic).
C#
The time complexity is generally higher than BFS due to the additional computation for the heuristic, but edges are still cut off through pruning. The space complexity remains similar to the previous method because of visited state cache retention.
| Approach | Complexity |
|---|---|
| Breadth-First Search with State Tracking | The time complexity is O(m * n * k) because we process each cell at most k times (once for each possible count of removed obstacles). The space complexity is also O(m * n * k) due to the visited array used for tracking states. |
| A* Search Algorithm | The time complexity is generally higher than BFS due to the additional computation for the heuristic, but edges are still cut off through pruning. The space complexity remains similar to the previous method because of visited state cache retention. |
Shortest Path in a Grid with Obstacles Elimination | Live Coding with Explanation | Leetcode - 1293 • Algorithms Made Easy • 16,844 views views
Watch 9 more video solutions →Practice Shortest Path in a Grid with Obstacles Elimination with our built-in code editor and test cases.
Practice on FleetCode