1184. Every Way Down and Right
A grid of r rows and c columns has free cells written . and blocked cells
written #. Starting at the top-left cell, reach the bottom-right cell using
only single steps DOWN and RIGHT, never entering a blocked cell. Print every
route.
3 3 the two routes avoiding the blocked centre
... -> DDRR
.#. RRDD
...
## What most people try first
Count the routes with the usual grid formula, ways[i][j] = ways[i-1][j] +
ways[i][j-1], and then try to recover the routes from the table. That table is
the right tool for the COUNT and the wrong tool for the routes. It stores how
many routes reach a cell, not which ones, and the information needed to rebuild
them was thrown away when the two numbers were added together. Every route is a
distinct object, so there is nothing to add up and nothing to reuse.
## The method
Walk the grid, carrying the moves made so far:
go(i, j):
if (i, j) is the bottom-right cell: record cur; return
for each of (D, down), (R, right):
(ni, nj) = the neighbour
if it is inside the grid and not blocked:
cur.push(the letter); go(ni, nj); cur.pop()
The pop is the undo. Nothing else in this problem needs undoing, because a
step down or right can never return to a cell already on the route: both
coordinates only increase. That is what makes this the right place to start.
There is no visited grid here at all, and the next problem shows what changes
when the moves can go backwards.
## Why it is correct
Every down-and-right route from the top-left to the bottom-right is a sequence
of r - 1 downs and c - 1 rights, and the search builds exactly those
sequences, one move at a time, cutting a branch only when the next cell is off
the grid or blocked. A cut branch contains no valid route, because a route
cannot leave the grid and cannot pass through a blocked cell. So nothing valid
is lost and nothing invalid is kept.
## The output convention
A route is described by the moves that make it, as a string over D for a step
down and R for a step right. Every route here has exactly r + c - 2 moves.
Routes are printed one per line in LEXICOGRAPHIC order, which, since D comes
before R, is exactly the order produced by trying D before R at every
cell. So no sorting is needed at the end, and none is allowed to matter: the
order is part of the answer.
A grid with one cell needs no moves at all, and that empty route prints as the
word empty. If there is no route, print none.
## The settled boundaries
If the top-left or the bottom-right cell is itself blocked there is no route,
so print none. A one-by-one grid is already finished before any move, so its
answer is the single empty route and prints as empty. Both are in the tests.
## Cost
The number of routes is at most C(r + c - 2, r - 1), which is 924 at the
stated limit, and the search does O(r + c) work per route plus a constant per
abandoned branch.
Constraints - `1 ≤ r, c ≤ 7` - Every character of the grid is `.` or `#`.
Input
The first line contains two integers r and c.
The next r lines each contain c characters with no spaces, . for a free
cell and # for a blocked one.
Output
Print every route on its own line, as a string over D and R, the lines in lexicographic order. An empty route prints as empty. If no route exists, print none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.