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

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.

• It's not that simple. The problem is that in order to aggregate neighbors, you have to compare such objects. And you don't know whether (5,true) is smaller or greater than (6,false). – Veky Sep 3 '20 at 11:20
• @Veky that doesn't really matter, the relative comparison for the priority queue only needs to underestimate the actual cost to the finish (the heuristic). Many maze heuristics are straight-line and ignore walls anyway so the flag doesn't matter. – ratchet freak Sep 3 '20 at 12:03
• I'm not speaking about heuristic, I'm speaking about how to select the next node. Then you have to add the actual cost, and select the one with minimal total cost, not the one with minimal heuristic. – Veky Sep 3 '20 at 12:24
• the cost since start is accumulated, so you can decide on whatever the actual cost is of breaking a wall in addition of moving, for example you can make it half, then (5, true) has cost 5.5 and (6, false) has cost 6.0 and you pick the node that had the shorter path first but cannot break through the wall and afterwards the other node is still in the queue for picking later. That's what the last paragraph in my answer was about. – ratchet freak Sep 3 '20 at 12:32

Introduction

While solving google foobar I stumbled upon this problem. I approached the problem with A* along with a few modifications. As this algorithm correctly outlines the core concepts, I would like to go further ahead and add some detailing to this.

Algorithm:

Each node will have the following parameters:

1. parent: The immediate parent of the node.
2. position: This is the (x,y) position of the node.
3. f,g,h: These are the heuristics needed for A* to work.
4. wall_broken: This is a boolean flag that would account for a broken wall in the path to the node. By default is set to False.

After we set up our pre-requisites, we move into the algorithm.

1. Create the start and end node.
2. Initialize the open and closed lists. The open list must contain the start node.
3. Iterate until we have visited each node.
1. Take the node with least f from the open list. This is our current node. Remember putting it inside the visited list.
2. Check whether the current node is the end node. When comparing equality, we will compare the positions of the nodes only. If yes, then hurray! Return the path that has been traced. If no, perform the next step.
3. Generation of children from the current node.
• Check for validity of the position.
• Check if the position has a wall. If it does, then we need to check whether the current node has any broken walls in its path (this is where we will need the wall_broken property of the node). We destroy the wall if we have no prior destruction. We make sure to assign the wall_broken property of the child which broke into a wall to True.
• We do not generate children if they already have been visited.
4. Iteration on the children to decide which goes into the open list and which don't.
• Assign heuristics to each child.
• Look for a better child in open to replace. Else add it into the open list.

Conclusion

This algorithm is a modification of the A*. It conveys the core concept. If you want a detailed walkthrough of the concept with code, I have a gist written in python.