Shortest path when you may break up to k walls
Asked at Two Sigma
In a grid, 0 is open and 1 is a wall. You start at the top-left and want the bottom-right, moving up/down/left/right one cell per step. You may remove at most k walls along the way.
grid = [[0, 0, 0],
[1, 1, 0],
[0, 0, 0],
[0, 1, 1],
[0, 0, 0]]
k = 1
-> 6
Return the minimum number of steps to reach the bottom-right, or -1 if impossible.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.