1650. Fewest Signs to Repoint

A warehouse floor is a grid of r rows and c columns. Each square holds one of five values:

1 a sign pointing right 3 a sign pointing down 0 a blocked square 2 a sign pointing left 4 a sign pointing up

A trolley on a square may move to any of its four orthogonal neighbours that is on the floor and not blocked. Moving in the direction the square's sign points is free. Moving any other way means repointing that sign first, which costs 1.

Print the fewest signs that must be repointed to get the trolley from the top-left square to the bottom-right square.

1 1 3 1 1 3 -> 0 right, right, down, down, every move already signed 1 1 1

## The four things that have to be said

directed? the MOVES are, because a square's sign points one way, but the floor itself is not: both squares of a neighbouring pair can be entered, at their own prices. 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. A blocked square may seal the target off, or an endpoint may itself be blocked. Print -1 for both. A 1 by 1 floor of one unblocked square answers 0.

Note that repointing is permanent only in the story; the trolley passes each square at most once on a cheapest route, so there is no state to carry.

## What most people try first

Following the signs, since that is free, and repointing only when stuck. That is a greedy walk and it fails because a free move can lead into a corner while a single repointing opens a long free run. The floor 2 2 2 / 2 2 2 has no free move available from the top-left at all, and the answer is 3 rather than the 1 a stuck-then-repoint walk reports.

The second instinct is Dijkstra, which is right. It is also a heap maintaining an order over keys that take only two values.

## The method

Build the graph with one vertex per unblocked square. For each unblocked neighbour v of u, the edge u -> v has weight 0 when v lies in the direction u's sign points, and weight 1 otherwise. Then run a 0-1 breadth-first search from the top-left square.

pop u from the FRONT of the deque for each of the four neighbours v of u that is on the floor and unblocked: w = 0 if v is where u's sign points, else 1 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 deque is enough, and why the direction of the push matters

The deque holds at most two distinct distances at any moment, d and d + 1, and never out of order. Popping u at distance d, a free move writes d, which is already the smallest value in the deque and so belongs at the front; a repointed move writes d + 1, already the largest, so it belongs at the back. Both pushes preserve the ordering, so the front is a genuine minimum.

Push a free move on the BACK instead and the ordering breaks: a vertex at distance d would sit behind vertices at d + 1, so a larger distance would be settled first, and that is exactly the assumption Dijkstra's correctness rests on.

## Cost

O(r * c), which is 90000 squares at the limits, with O(r * c) memory for the distances and the deque. The answer is at most the number of squares, so a 32 bit integer is ample.

Constraints - `1 ≤ r ≤ 300` - `1 ≤ c ≤ 300` - Every character is one of `0`, `1`, `2`, `3`, `4`.