# Shortest path in a grid with turnstile

Short answer: Encode the maze as a directed graph and apply your usual Dijkstra or A*, ignoring the state you leave the turnstiles in. The turnstiles can be encoded by having arcs both ways on the sides without bar, and only the out going arc for the sides with bars.

For instance, this turnstile: Can be turned into this graph portion: Of course, don’t connect the center node to its neighbor if it’s not reachable (like a wall).

Long answer:

The essential property that make it work is that shortest paths never include cycles, even with those turnstiles.

Claim: Shortest path don’t include cycles.

Idea of the proof:

Let’s assume the shortest path $$P$$ between nodes $$A$$ and $$B$$ visit the same node $$N_1$$ twice. For $$P$$ to be the shortest path, there must be a node $$N_2$$ that we can access on the second visit to $$N_1$$ but not on the first visit. Otherwise reaching $$N_2$$ from $$N_1$$ on the first visit would lead to a path shorter than $$P$$.

But this situation cannot exist because unlocking the way between $$N_1$$ and $$N_2$$ requires visiting the blocking turnstile(s). Therefore there’s no need to revisit $$N_1$$ to access $$N_2$$.

Then it follows that:

• When looking for a shortest path, there’s no need to consider revisiting nodes.
• Thus the rotation of the turnstiles already visited can be completely ignored.
• Since there is no additional state to keep track of, the usual Dijkstra or A* can be used.