Shortest Path in a Grid with Obstacles Elimination
To find the shortest path from the upper left corner to the lower right corner, given that you can eliminate at most k obstacles, you can use a Breadth-First Search (BFS) with a small modification to handle the obstacles.
|
|
This code defines a BFS that visits every cell with a different remaining k
separately. If it encounters an obstacle, it reduces k
by 1, but only if there is at least one k
left. If it reaches the destination, it returns the number of steps taken. If the queue becomes empty without reaching the destination, it returns -1.
The time complexity of this solution is O(m * n * k), where m is the number of rows, n is the number of columns, and k is the number of allowed obstacle eliminations. The space complexity is also O(m * n * k) due to the visited set and the queue.