Shortest Path in a Changing Maze

Stable Maze

Given a maze (2D grid), 0s represent roads and 1s represent walls. What is the shortest path (minimum number of steps) that you can go from the starting point to the end point?

Example

I:
0 0 0 0
0 1 0 0
0 0 1 0
0 1 1 0
O: 5

Mutable Maze with One Bomb

Now you are given a bomb that you can knock down a wall. What is the minimum number of steps now?

Example

I:
0 0 0 0
0 1 0 0
0 0 1 0
0 1 1 0
O: 5

Mutable Maze with K Bombs

Now you are give k bombs. What is the minimum number of steps?

Example

I: M, k = 2
O: 4

Because this is a minimization problem and we are only storing a number we can try DP. And there is indeed an optimal substructure and overlapping subproblems (each layer).