1648. Fewest Staircases Through the Building

A floor plan is a grid of r rows and c columns. A . is a room you may walk into and a # is solid wall.

Moving SIDEWAYS between two adjacent rooms is free, because it is a corridor. Moving UP or DOWN between two adjacent rooms costs 1, because it is a staircase. Print the fewest staircases needed to get from the top-left room to the bottom-right room.

..... ####. -> 2 walk right along row 1, then two staircases down column 5 .....

## The four things that have to be said

directed? no. Every corridor and staircase works both ways. self-loops? there are none: a move always changes cell. parallel edges? there are none: two adjacent rooms are joined once. unreachable? yes, and in two ways. The walls may cut the building in two, or an endpoint may itself be a wall. Print -1 for both. A 1 by 1 building of one room answers 0.

## What most people try first

Breadth-first search over the four moves, which is what problem 375 wants. It is wrong here for a reason the grid hides: a queue counts MOVES, and sideways moves are free. On the example above, breadth-first search prefers a route of six moves to a route of eight, while the eight-move route uses fewer stairs.

The second instinct is Dijkstra, which is correct. It also carries a heap for weights that are only ever 0 or 1.

## Where the cost sits, which is the difference from problem 546

Problem 546 puts the cost on the CELL: entering an obstacle costs one removal, so two routes through the same cells cost the same however they were entered. Here the cost sits on the MOVE. The same two rooms can be joined freely sideways and expensively vertically, so the route's shape and not merely its set of cells decides the price.

## The method

Number cell (i, j) as i * c + j and run a 0-1 breadth-first search:

dist[top-left] = 0 deque holding the top-left cell pop from the front; for each of the four neighbours that is a room: w = 0 for a sideways move, 1 for a vertical move if dist[u] + w < dist[v]: dist[v] = dist[u] + w push v on the front if w == 0, else on the back

Pushing a zero-cost neighbour on the front is what keeps the queued distances non-decreasing, because that neighbour's distance equals the one just popped and so is already the smallest value present. A one-cost neighbour is d + 1, the largest present, so it belongs at the back. The front therefore always holds a true minimum and no heap is needed.

## Cost

O(r * c) time and memory: 90000 cells at the limits. The answer is at most r - 1 vertical moves times c, far inside a 32 bit integer.

Constraints - `1 ≤ r ≤ 300` - `1 ≤ c ≤ 300` - Every character is `.` or `#`.