1654. Fewest Doors to Unlock

A floor is a grid of r rows and c columns. A . is an open square, a # is solid wall, and a + is a locked door that may be unlocked for one key.

Walking onto an open square is free. Walking onto a door costs one key, charged once as you enter it. Walls can never be entered. Print the fewest keys needed to get from square (sr, sc) to square (tr, tc), moving up, down, left or right.

If the starting square is itself a door, that door is charged too.

. + . + + + from (1,1) to (3,3) -> 2 . + .

Every route out of the top-left corner crosses at least two doors, and . + . + along the top row and down the right edge crosses exactly two.

## The four things that have to be said

directed? no. Every move works both ways. self-loops? there are none: a move always changes square. parallel edges? there are none: two neighbouring squares are joined once in each direction. unreachable? yes, in two ways: an endpoint may be a wall, or the walls may seal the target off. Print -1 for both. When the start and the target are the same open square the answer is 0.

## What most people try first

Breadth-first search, counting moves and hoping doors come out even. They do not: the point is to trade length for keys, and the route with the fewest moves through the example crosses three doors, not two.

Problem 546 is the closest relative in the bank and it is a different question. There the grid has two kinds of square and the route runs corner to corner; here a third kind of square can make the target genuinely unreachable, and the endpoints are given, so the start may be a door and must be paid for.

## The cost is on the square entered, so it is on the edge

Give the move into square v the weight 1 when v is a door and 0 when v is open. Walls contribute no edge at all. Every weight is 0 or 1, which is the signal to use a deque rather than a heap.

dist[start] = 0 deque holding start pop u from the FRONT for each of the four neighbours v that is not a wall: w = 1 if v is a door else 0 if dist[u] + w < dist[v]: dist[v] = dist[u] + w push v on the FRONT if w == 0, else on the BACK answer = dist[target], plus 1 if the start itself is a door

## Why the deque stays sorted

The distances inside it never decrease from front to back and span at most d and d + 1. Popping u at d, a move onto an open square writes d, already the smallest value present, so it belongs at the front; a move onto a door writes d + 1, already the largest, so it belongs at the back. The front is therefore always a true minimum, and that is all Dijkstra's argument needs.

## The charge on the starting square

The search measures doors ENTERED, and the start is never entered, so it is never counted. Add one at the end when the starting square is a door. Folding that into dist[start] instead also works, but only if the comparison that settles the start is written to allow it.

## Cost

O(r * c) time and memory, 90000 squares 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` - `1 ≤ sr, tr ≤ r` - `1 ≤ sc, tc ≤ c` - Every grid character is `.`, `#` or `+`.