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.
b. Describe an algorithm (not necessarily linear-time) that finds 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.