CODEWITHSUNDEEP
algorithmdijkstrashortest-path
nkt
nkt

Reputation: 403

Shortest path in maze allowing to go through a limited number of walls?

Without the ability to go through walls, I figured it is a standard Dijkstra's problem. However, if I were given X times to bypass/go through walls, how can I model it to apply Dijkstra's algorithm?

Upvotes: 1

Views: 727

Answers (1)

deinst
deinst

Reputation: 18782

Assuming that your maze is represented as a graph: Create X + 1 copies of the graph, and create a directed edge between level i and level i + 1 for cells that are adjacent with a wall between them. Finally merge all of the exits.

From a practical point of view, of course you do not need to create copies of the graph, just keep track of ordered pairs of (vertex, level).

Upvotes: 7

Related Questions