patternMinor
Shortest path in a maze where you can break one wall
Viewed 0 times
pathcanyoushortestwallmazewhereonebreak
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#92368, answer score: 4
Revisions (0)
No revisions yet.