1185. Every Route That Never Crosses Itself

Same grid as problem #1184, free cells . and blocked cells #, but now a step may go in any of the four directions: down, left, right or up. A route starts at the top-left cell, ends at the bottom-right cell, and may not enter any cell twice. Print every route.

2 2 the two routes around the square .. -> DRU .. RDL

## What most people try first

Reuse the answer to #1184 with four directions instead of two. It does not terminate. With only down and right, both coordinates increase on every step, so a route cannot return to a cell it has already used and the search is automatically finite. Add left and up and the search walks in circles forever: right, left, right, left.

So the thing that was free in #1184 now has to be paid for. The route needs to remember which cells it is standing on.

## The mark that has to be released

A cell must be marked on the way in and UNMARKED on the way out. Marking and never releasing is the characteristic bug of this whole topic: it finds some routes and silently misses others, because a dead end leaves cells marked that a later route needed. Problem #1150 states that rule; here it is measurable, because a missing unmark changes the number of lines you print rather than one yes or no.

## The method

A boolean grid seen, set when a cell is entered and cleared when it is left:

go(i, j): if (i, j) is the bottom-right cell: record cur for each of (D, down), (L, left), (R, right), (U, up): (ni, nj) = the neighbour if inside and not blocked and not seen[ni][nj]: seen[ni][nj] = true; cur.push(the letter) go(ni, nj) cur.pop(); seen[ni][nj] = false

Two details are easy to get wrong. The starting cell must be marked before the first call, or a route can step back onto it. And there is no return after recording, because in general a target may lie partway along a longer route. Here the target is a corner, so nothing can continue through it, but writing the return teaches a habit that is wrong everywhere else.

## Why it is correct

The claim is that seen describes exactly the cells on the current route, at every node of the search. It holds at the start, where the route is the single starting cell and only that cell is marked. Each step marks the cell it enters immediately before descending and clears it immediately after returning, so the property is preserved by every step and restored by every undo. Given that, a neighbour is offered precisely when it is a free cell not already on the route, which is the definition of a legal step. So the leaves of the search are precisely the self-avoiding routes.

## The output convention

A route is described by the moves that make it, as a string over D down, L left, R right and U up. Routes have different lengths here, so lines are compared as strings: a route that is a prefix of another comes first, and otherwise the first differing character decides, with D before L before R before U.

That is exactly the order a depth-first search produces when it tries the four directions in that order and records a route at the moment it arrives, because such a search reaches every prefix before any of its extensions. So no sorting is needed, and the order is part of the answer rather than an accident of your loop.

A route of no moves prints as the word empty. If there is no route at all, print none.

## The settled boundaries

A one-by-one grid starts where it ends, so its answer is the single empty route and prints as empty. If the top-left or the bottom-right cell is blocked the answer is none.

## Cost

There is no useful closed form. The count grows very fast: an open grid of 2 by 2 has 2 routes, 3 by 3 has 12, and 4 by 4 has 184. The search does constant work per node and the node count is proportional to the number of partial routes, so the cost is the answer size, which is why the grid is capped at 4 by 4.

Constraints - `1 ≤ r, c ≤ 4` - Every character of the grid is `.` or `#`.