Break Through Walls
grid is a rectangular grid of 0 (open) and 1 (wall), given as a list of rows. You start in the top left cell, which is always open, and want to reach the bottom right cell. One move goes up, down, left or right to a neighbouring cell inside the grid.
You carry a hammer that can break at most k walls: moving onto a wall cell breaks it and uses up one break. The bottom right cell may itself be a wall. A broken wall stays open afterwards, though a shortest route never returns to a cell anyway. Return the smallest number of moves needed to reach the bottom right cell, or -1 if it cannot be done. A grid with a single cell needs 0 moves.
Example 1
Break the wall to the right of the start, then walk along the top row and down the right column: 4 moves.
Example 2
Without any break the start is boxed in by two walls.
Constraints
1 <= rows, cols <= 10grid[r][c]is0or1, andgrid[0][0] == 00 <= k <= 10
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.