1664. The Smallest Shortest Set of Moves

A maze is a grid of r rows and c columns of . for open and # for wall. A move goes to an orthogonal open neighbour and is written as one letter:

D down L left R right U up

Print the moves of a shortest route from the top-left square to the bottom-right square, as one string with no spaces. Among all routes using the fewest moves, print the string that is smallest in dictionary order, where the letters compare as D < L < R < U.

Print none if no move is needed at all, and -1 if there is no route.

. . . . . . -> DDRR . . .

Four moves are needed. DDRR beats DRDR, RDDR, RRDD and the rest because D sorts before R.

## The four things that have to be said

directed? no. Every move can be undone. self-loops? there are none: a move always changes square. parallel edges? there are none: two neighbours are joined once each way. unreachable? yes, in two ways: an endpoint may be a wall, or the walls may seal the target off. Print -1 for both. A 1 by 1 open maze prints the word none, since no move is made.

## Why a word is printed instead of an empty line

A route of no moves has an empty move string, and an empty line is indistinguishable from a crashed program. Printing none makes the case checkable, and that is the whole reason the output contract is stated separately from the story.

## What most people try first

Breadth-first search from the top-left, recording a parent per square, then reading the route back from the corner. That gives A shortest route, and which one depends on the order the four moves were tried, so two correct programs disagree. The question has to be pinned, and once it is, the parent array is the wrong tool: it records where the search came from, not what the dictionary rule wants.

Sorting the four moves alphabetically and following them greedily from the start is the next idea. It walks into dead ends, because an alphabetically early move may lead somewhere from which the corner is further away.

## Distances TO the corner, then walk greedily

Run breadth-first search from the BOTTOM-RIGHT square, giving distT, the fewest moves from each square to the corner. Then:

at square s, in the order D, L, R, U: take the first move whose destination t is open and has distT[t] == distT[s] - 1 append its letter, move to t

## Why greedy on the target distances is exactly the dictionary minimum

A move to a square with distT[t] == distT[s] - 1 keeps the route shortest, because the rest can still be done in distT[t] moves. So every such move is extendable to a shortest route, and no later letter can make up for an alphabetically larger letter now. Taking the earliest available letter at each step therefore gives the smallest string.

The walk makes exactly distT of the start square's moves and cannot loop, since distT drops by one each time.

## A different tie-break from problem 1669

The order here is on the LETTERS, and problem 1669 orders the same kind of route by its COORDINATES. They are not the same rule: from (1, 1) the move D leads to (2, 1) and R leads to (1, 2), so the letter rule prefers D while the coordinate rule prefers (1, 2) and therefore R. The two problems exist as a pair to make that concrete.

## Cost

O(r * c) for the search and O(r * c) for the walk, with 90000 squares at the limits. No total ever exceeds the number of squares, so 32 bit arithmetic is ample throughout.

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