# Shortest path in a maze where you can break one wall

How would I solve the following problem?

You have maps of parts of the space station, each starting at a prison exit and ending at the door to an escape pod. The map is represented as a matrix of 0s and 1s, where 0s are passable space and 1s are impassable walls. The door out of the prison is at the top left (0, 0) and the door into an escape pod is at the bottom right (w−1, h−1). Write a function that generates the length of a shortest path from the prison door to the escape pod, where you are allowed to remove one wall as part of your remodeling plans.

I know that without destroying the walls this could be easily solved with the use of Dijkstra. But how to take into account the fact I can destroy one wall?

The only solution I could come up with was to remember two distances for each node: one distance is the "real" shortest path, the second one is the shortest past when I break one (any) wall.

At first I would count all the "real" shortest paths with classic Dijkstra. In the second run I would use Dijkstra again to compute the second parameter of each node: shortest path with exactly one wall broken.

In each iteration the closest node to be chosen (I need to check even vertices that are "one wall away") in Dijkstra is the one with the shortest "real" path or path with a broken wall (whichever is smaller). In case the vertex is one wall away, I only check the "real" path property of course.

This seems correct to me. But is there a better (more efficient) solution?

• See cs.stackexchange.com/q/66116/755, cs.stackexchange.com/q/53192/755 and apply those ideas to your problem. – D.W. May 26 '18 at 21:17
• Thank you for the link. It definitely tells me how to do this using Dijkstra, but they also mention Bellman-Ford would be much better in this case. I am asking for an efficient solution, so this doesn't entirely answer my question. – SlowerPhoton May 26 '18 at 21:45
• Keep thinking about it -- those ideas do lead to an efficient solution. And I'm pretty skeptical of the claim made by your source. Dijkstra is definitely the way to go; Bellman-Ford will be far slower. With Dijkstra you can solve this problem in linear time, whereas Bellman-Ford's runnign time is quadratic time, so I'm not sure what they have in mind. – D.W. May 26 '18 at 21:52
• Well, maybe there is a way Bellman-Ford doesn't need to construct that graph, but anyway I believe the construction of the graph they mention must be in $O(|V| + |E|)$ (for my $k=2$), right? – SlowerPhoton May 26 '18 at 22:03