1. Suppose that walls in the maze can be knocked down, with a penalty of P squares. P is speci?ed as a parameter to the algorithm. (If the penalty is 0, then the problem is trivial.) Describe an algorithm to solve this version of the problem. What is the running time for your algorithm?

2. Suppose that the maze may or may not have a solution.

a. Describe a linear-time algorithm that determines the minimum number of walls that need to be knocked down to create a solution. (Hint: Use a double-ended queue.)

b. Describe an algorithm (not necessarily linear-time) that ?nds a shortest path after knocking down the minimum number of walls. Note that the solution to part (a) would give no information about which walls would be the best to knock down.