1652. Free Portals in the Maze

A maze is a grid of r rows and c columns of . for open and # for wall. There are also p PORTALS. Portal k joins two open squares and may be used in either direction, instantly and for nothing.

A step to an orthogonal open neighbour costs 1 minute. Using a portal costs nothing. Print the fewest minutes to get from the top-left square to the bottom-right square.

. # . . # . with a portal joining (2,1) and (2,3) -> 2 . # .

Step down to (2,1) for one minute, portal across for nothing, step down to (3,3) for one minute. Without the portal the wall down the middle makes the target unreachable.

## The four things that have to be said

directed? no. Steps and portals both work in either direction. self-loops? a portal may join a square to itself, which is harmless and changes nothing. parallel edges? allowed. Two portals may join the same pair of squares, and the second is redundant rather than wrong. unreachable? yes, and in two ways: an endpoint may itself be a wall, or the walls may seal the target off even with the portals. Print -1 for both. A 1 by 1 open maze answers 0.

## What most people try first

Breadth-first search over steps alone, treating a portal as a thirteenth kind of move that also takes a minute. That is the natural reading and it overcounts: on the example it answers 4 rather than 2.

Fixing that by making a portal a zero-cost move inside a plain queue is worse, because a queue has no way to settle a zero-cost arrival before the one-cost arrivals already waiting in front of it. It can report a square as four minutes away when a free portal puts it two minutes away, and it does so silently.

Dijkstra with a heap is correct. It is also O(m log m) for weights that take only the values 0 and 1.

## The method

One vertex per open square, numbered i * c + j. Grid steps between open neighbours get weight 1. Each portal gets a pair of weight-0 edges between its two squares. Then run a 0-1 breadth-first search from the top-left square.

dist[start] = 0 deque holding start pop u from the FRONT for each neighbour v through an edge of weight w: if dist[u] + w < dist[v]: dist[v] = dist[u] + w push v on the FRONT if w == 0, else on the BACK

## Why the front push is what makes it work

The invariant: the distances inside the deque do not decrease from front to back, and span at most two consecutive values d and d + 1.

Pop u at distance d. A portal writes d into the square at the other end. d is already the smallest value in the deque, so that square belongs at the FRONT and will be settled before anything at d + 1. A step writes d + 1, already the largest value, so it belongs at the BACK. Neither push can disturb the ordering, so the front is always a genuine minimum and no two keys are ever compared. Push the portal arrival on the back instead and a square at d waits behind squares at d + 1, which is exactly the ordering Dijkstra's correctness forbids.

## Cost

O(r * c + p) time and memory: 90000 squares and 50000 portals at the limits. The answer is at most the number of squares, so a 32 bit integer is ample.

Constraints - `1 ≤ r ≤ 300` - `1 ≤ c ≤ 300` - `0 ≤ p ≤ 50000` - Every grid character is `.` or `#`. - Both squares of every portal are open.