Loading problem...
You are given an m × n integer matrix called grid, where each cell contains either 0 (representing a passable empty cell) or 1 (representing a blocked obstacle). Your goal is to navigate from the top-left corner at position (0, 0) to the bottom-right corner at position (m - 1, n - 1).
You can move in four cardinal directions: up, down, left, or right. Each movement to an adjacent cell constitutes one step. You may only move into cells within the grid boundaries.
Here's the twist: you possess the ability to remove obstacles. You are given an integer removalLimit which represents the maximum number of obstacles you are allowed to eliminate during your traversal. When you remove an obstacle, that cell becomes passable, and you can move through it.
Your task is to determine the minimum number of steps required to reach the destination, utilizing at most removalLimit obstacle removals. If there is no valid path that can reach the destination even after using all available obstacle removals, return -1.
Key Observations:
(0, 0) and the destination cell (m - 1, n - 1) are guaranteed to be empty (value 0).grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]]
removalLimit = 16Without removing any obstacles, the shortest path requires 10 steps by navigating around all blockers. However, by eliminating the obstacle at position (3,2), we can take a direct route: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (3,2) → (4,2). This path requires only 6 steps while using exactly 1 obstacle removal.
grid = [[0,1,1],[1,1,1],[1,0,0]]
removalLimit = 1-1With only 1 obstacle removal allowed, there is no possible path from the top-left to the bottom-right. The grid is too densely blocked, requiring at least 2 obstacle removals to create any viable route. Therefore, we return -1.
grid = [[0,0,0],[0,0,0],[0,0,0]]
removalLimit = 14The grid has no obstacles at all, so no removals are needed. The Manhattan distance from (0,0) to (2,2) is 4 steps, which is the optimal path: move right twice and down twice (or any equivalent combination).
Constraints