1188. Down and Right to an Exact Total
Every cell of an r by c grid holds a value. A route goes from the top-left
cell to the bottom-right cell using only steps DOWN and RIGHT, and its total is
the sum of every cell it stands on, both ends included. Print every route whose
total is exactly t.
3 3 t = 5 every route over a grid of ones
1 1 1 visits 5 cells, so all six qualify
1 1 1 -> DDRR DRDR DRRD RDDR RDRD RRDD
1 1 1 printed one per line
## What most people try first
Enumerate every route as in #1184, add up each one afterwards, and keep the
ones that match. That is correct and it is the baseline this problem is built
to beat. It does O(r + c) work per route for the addition and, more
importantly, it does the full work for routes that were already hopeless after
two steps.
## The method, and the prune that is actually valid
Carry the running total down the recursion instead of recomputing it, and cut a
branch the moment the total passes t:
go(i, j, tot): # tot includes the value at (i, j)
if tot > t: return
if (i, j) is the bottom-right cell:
if tot == t: record cur
return
for each of (D, down), (R, right):
cur.push(the letter); go(ni, nj, tot + value[ni][nj]); cur.pop()
## Why the prune is correct, and when it would not be
The cut is valid because of one fact, and it is stated in the constraints:
every value is at least 0. The running total along a branch is therefore
monotone, never decreasing, so once it exceeds t no extension can ever bring
it back down and the whole subtree is dead.
Change the constraint to allow a single negative value and this prune becomes
WRONG, not merely weaker. A total of 11 against a target of 5 can be rescued by
a later cell holding -6, so cutting there loses real routes. That is not a
hypothetical: problem #1175 is the version of this question with negative
values allowed, and it needs a two-sided bound over the remaining cells instead
of a one-sided test on the total so far. A prune is only as sound as the
property it leans on, and the property has to be in the constraints.
## 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 has the single empty route, whose total is the value of that
one cell. So it prints empty if that value equals t and none otherwise,
and both cases are tested. A target of 0 is reachable only when every cell on
some route holds 0.
## Overflow
A route visits at most 13 cells and each holds at most 1000, so no total exceeds 13000. That is nowhere near the 2147483647 a signed 32 bit integer holds, and a plain int is the right type. There is no overflow here and the problem does not pretend otherwise.
## Cost
The same C(r + c - 2, r - 1) routes in the worst case, but the prune removes
whole subtrees as soon as the total is too big, so a grid of large values with a
small target finishes almost immediately while the unpruned enumeration does
not.
Constraints - `1 ≤ r, c ≤ 7` - `0 ≤ t ≤ 20000` - `0 ≤ value of a cell ≤ 1000`
Input
The first line contains three integers r, c and t.
The next r lines each contain c integers separated by spaces.
Output
Print every qualifying 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 qualifies, print none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.