Daily bit(e) of C++ | Shortest path with obstacle removal
Daily bit(e) of C++ #91, Common interview problem: Shortest path with obstacle removal
Given a 2D grid of size m*n, containing 0 (space) and 1 (obstacle), determine the shortest path from the coordinate {0,0} to {m-1,n-1}, given that you can remove up to k obstacles.
If no path exists, return -1.
For example, in the above grid, we must remove at least two obstacles to reach the end. Once we do, the length of the minimum path is 8.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/joa9cM3fb.
Solution
Finding the shortest path is a canonical problem for the breadth-first search algorithm. The tricky part, of course, is dealing with removing obstacles.
However, consider the following. What if removing an obstacle would instead move us to another floor of the maze where this obstacle doesn’t exist? In such a case, we can consider the k as another dimension to the maze, allowing us to go k-floors deep.
Since we are using breadth-first search, we will never revisit a space, meaning we also do not care which obstacle we removed, only how many.
