Practice/Meta/Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination

Leetcode 1293. Shortest Path in a Grid with Obstacles Elimination

CodingMust

Problem

You are given a 2D grid where each cell contains either 0 (empty space) or 1 (obstacle). Your goal is to navigate from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) using the minimum number of steps.

At each position, you can move in one of four directions: up, down, left, or right. Each move counts as one step.

You have the ability to remove up to k obstacles during your journey. When you encounter an obstacle, you can choose to remove it and continue through that cell, consuming one of your removal allowances.

Return the minimum number of steps needed to reach the destination. If it's impossible to reach the destination even with k removals, return -1.

Requirements

1. Implement a function that finds the shortest path from top-left to bottom-right
2. Account for the ability to remove up to k obstacles along the way
3. Return the minimum step count, or -1 if no valid path exists
4. Handle edge cases including single-cell grids and grids with no obstacles

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 40
• 1 <= k <= m * n
• grid[0][0] == grid[m-1][n-1] == 0
• Each cell in the grid contains either 0 or 1

Examples

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 is: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) → (3,2) → (4,2) This path goes around most obstacles and doesn't require any removals.

Example 2:

Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 Output: -1 Explanation: Even with one obstacle removal, we cannot create a path from (0,0) to (2,2). We would need to remove at least 2 obstacles.

Example 3:

Input: grid = [[0,0,0],[0,0,0],[0,0,0]], k = 0 Output: 4 Explanation: No obstacles exist, so we simply move right 2 steps and down 2 steps.