9.48 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-tim e) 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. (Hint: Use Exercise 9.47.) - | |
| View Solution | |
| << Back | Next >> |