# 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

## 2 Answers

No. There is not a more efficient solution. It's possible to solve the problem in linear time using two iterations of Dijkstra's algorithm, if you implement the second run appropriately (which doesn't seem to be described in the question; but I will assume you know how to do it). You can't do better than linear running time; any algorithm will have to examine all of the input (or at least a constant fraction of it). Therefore, there is no possibility of an algorithm that is asymptotically better; it's not possible to find an algorithm that is more than a constant factor faster.

I didn't verify your specific algorithm, because I couldn't understand the next-to-last paragraph of your question, but I do know the problem can be solved in linear time.

You can use any search algorithm (including A*) with a tiny alteration from the standard one.

In each node you store whether the path from the start has a broken wall or not. Then when generating the neighbours you can move into a wall only if that flag is false and the neighbours that move into a wall get it set to true.

When Comparing Nodes for equality (for replacing in the heap and or the closed set) that flag counts alongside the position.