1189. Down and Right With Exactly k Turns
A grid of r rows and c columns has free cells . and blocked cells #.
A route goes from the top-left cell to the bottom-right cell using only steps
DOWN and RIGHT, never entering a blocked cell. A TURN is a move that goes in a
different direction from the move immediately before it, so the first move is
never a turn. Print every route with exactly k turns.
3 3 k = 2 two routes change direction exactly twice
... -> DRRD
... RDDR
...
## What most people try first
Enumerate every route as in #1184, count the turns in each finished string, and filter. Correct, and it is the baseline. The interesting question is what has to be added to the search to filter DURING it rather than after, and that question is about state.
## The state this search needs
A plain route search carries the position. This one cannot decide whether the next move is a turn from the position alone, because a turn is defined by comparison with the previous move. So the state grows by exactly two things:
- the direction of the previous move, with a distinct value meaning "no move
- has been made yet"
- how many turns have been used so far
go(i, j, last, used):
if used > k: return
if (i, j) is the bottom-right cell:
if used == k: record cur
return
for each of (D, down), (R, right):
if inside and not blocked:
nextUsed = used + (1 if last exists and the letter differs else 0)
cur.push(the letter); go(ni, nj, the letter, nextUsed); cur.pop()
Getting the "no move yet" value wrong is the characteristic bug. If you
initialise last to D, then a route beginning with R is charged a turn it
did not make, and every answer for odd k is wrong while even k looks fine
on small grids. Use a value no move can equal.
## Why it is correct, and why the prune is sound
The turn count never decreases as a route grows, because each move adds either
0 or 1. So once used exceeds k no extension can get back to k, and
cutting there loses nothing. This is the same shape of argument as #1188's
total, and it depends on the same kind of monotonicity. The equality is only
checked at the bottom-right cell, so a route that reaches k turns early is
still explored, which it must be: it can continue straight for any number of
further moves.
## 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
A one-by-one grid makes no moves, so it has 0 turns. It therefore answers
empty when k is 0 and none for every larger k. Both are tested. A route
on a single row makes only rights and has 0 turns. An open grid has no route
with 0 turns at all unless it is a single row or a single column, because
reaching the opposite corner needs both a down and a right.
## Overflow
Nothing here grows: the turn count is at most r + c - 3 and the number of
routes at most 924. No wide type is needed anywhere.
## Cost
The search is the #1184 search with two extra state values and one extra cut,
so the worst case is the same C(r + c - 2, r - 1) routes, and small k is
very much faster than that because most subtrees die early.
Constraints - `1 ≤ r, c ≤ 7` - `0 ≤ k ≤ 12` - Every character of the grid is `.` or `#`.
Input
The first line contains three integers r, c and k.
The next r lines each contain c characters with no spaces, . for a free
cell and # for a blocked one.
Output
Print every route with exactly k turns 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 qualifies, print none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.