# UVa 10798

Jump to navigation Jump to search

## Summary

This is an exhaustive search problem, with the aid of some memoization.

## Explanation

Looking carefully at the search space, we note that for any ${\displaystyle N}$, the most roses we need to trample is simply ${\displaystyle {\frac {N}{2}}}$:

RRRRRRRRRRR
RRRRRRRRRRR
RRRRRRRRRRR
RRRRRRRRRRR
RRRRRRRRRRR
RRRRRPRRRRR
RRRRRRRRRRR
RRRRRRRRRRR
RRRRRRRRRRR
RRRRRRRRRRR
RRRRRRRRRRR


Since the field is full of roses (this is the worst case), we can't do worse than going in a straightline - and step on ${\displaystyle {\frac {N}{2}}}$ roses. Also, since ${\displaystyle N\leq 21}$, we can simply try all direction, and keep track (and then memoize the number of roses we would've stepped on, if we were looking that way. This gives us 6 dimensions to memo on, but since the numbers are so small, this should run in time.

## Input

11
...........
...........
...........
...........
....RRRRRR.
....RPRRRR.
....RRRRRR.
....RRRRRR.
....RRRRRR.
....RRRRRR.
...........
5
.RRR.
R.R.R
R.P.R
R.R.R
.RRR.
5
RR.RR
RR.RR
..P..
RR..R
RRR.R
9
RRRR.R.RR
RRRR.R.RR
R..R.R.RR
RRRR.R.RR
RRRRPRRRR
RR.RRRRRR
RR.RR....
RR.RRRRRR
RR.RRRRRR
9
RRRR.R.RR
RRRR.R.RR
R.RR.R.RR
RRRR.R.RR
RRRRPRRRR
RR.RRRRRR
RR.RR....
RR.RRRRRR
RR.RRRRRR
9
RRRR.R.RR
RRRR.R.RR
R.RR.R.RR
RRRR.R.RR
RRRRPRRRR
RR.RRRRRR
RR.RR....
RR.RRRRRR
RR.RRRRRR
21
RRRRRRRRRRRRRRRRRRRRR
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R.........P.........R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
R...................R
RRRRRRRRRRRRRRRRRRRRR
9
RRRR.RRRR
RRRR..RRR
RRRRR.RRR
R.....RRR
..R.P.R..
RRR.....R
RRR.RRRRR
RRR..RRRR
RRRR.RRRR
1
P
13
RRRRRR.RRRR.R
....R.R...R.R
RRRRR..RRRRRR
R.RRRRRR.RR.R
R.R..RR...RRR
R.RR....RR.RR
.R.R.RP.RRR..
R.RRR.R.RRRRR
..RR.R.R..R.R
R.RR.R.R.RR.R
R.RRRR.RRRRRR
R.R...R......
R.RRRRRR.RRRR
21
RRRRRRRR.RRRRRRRRRRRR
RRRRRRRR..RRRR...RRRR
RRRRR...R..RR..R.RRRR
RRRRR.R..R....R..RRRR
R...R..R..RRRR..RRRRR
R.R..R..R..RR..R...RR
R..R..R..R....R..R.RR
RR..R..R..RRRR..R..RR
RRR.RR.RR..RR..R..R..
RRR.RR.RRR.R..R..R..R
RR..R..R..P..R..R..RR
R..R..R..R.RRR.RR.RRR
..R..R..RR..RR.RR.RRR
RR..R..RRRR..R..R..RR
RR.R..R....R..R..R..R
RR...R..RR..R..R..R.R
RRRRR..RRRR..R..R...R
RRRR..R....R..R.RRRRR
RRRR.R..RR..R...RRRRR
RRRR...RRRR..RRRRRRRR
RRRRRRRRRRRR.RRRRRRRR
21
RRRRRRRR.RRRRRRRRRRRR
RRRRRRRR..RRRR...RRRR
RRRRR...R..RR..R.RRRR
RRRRR.R..RR...R..RRRR
R...R..R..RRRR..RRRRR
R.R..R..R..RR..R...RR
R..R..R..R....R..R.RR
RR..R..R..RRRR..R..RR
RRR.RR.RR..RR..R..R..
RRR.RR.RRR.R..R..R..R
RR..R..R..PR.R..R..RR
R..R..R..R.RRR.RR.RRR
..R..R..RR..RR.RR.RRR
RR..R..RRRR..R..R..RR
RR.R..R....R..R..R..R
RR...R..RR..R..R..R.R
RRRRR..RRRR..R..R...R
RRRR..R....R..R.RRRRR
RRRR.R..RR..R...RRRRR
RRRR...RRRR..RRRRRRRR
RRRRRRRRRRRRRRRRRRRRR
21
RRRRRRRR.RRRRRRRRRRRR
.RRRRRRR..RRRR...RRRR
..RRR...R..RR.RR.RRRR
...RR.RRRR....RRRRRRR
....R..RR.RRRR..RRRRR
.....R..R..RR..R...RR
......R..R....RR.RRRR
.......R..RRRR..R..RR
........R..RR.RR..R..
.........R.R..R..R..R
..........P..R..R..RR
.........R.RRR.RR.RRR
........RR.RR..RR.RRR
.......RRRR..R..R..RR
......RRR..R..R..R..R
.....R.RRR..R..RR.RRR
....R..RRRR..R..R...R
...R..RR...RR.R.RRRRR
..RR.R..RR..R...RRRRR
.RRR.R.RRRR..RRRRRRRR
RRRRRRRRRRRR.RRRRRRRR
21
.................R.R.
RRRRRRRRRRRRRRRRRR.R.
.................R.R.
RRRRRRRRRRRRRRRR.R.R.
.R.............R.R.R.
.R.RRRRRRRRRRR.R.R.R.
.R.R.........R.R.R.R.
.R.R.RRRRRRR.R.R.R.R.
.R.R.R.....R.R.R.R.R.
.R.R.R.RRR.R.R.R.R.R.
.R.R.R.R..P..R.R.R.R.
.R.R.R.R.R.RRR.R.R.R.
.R.R.R.R.R.....R.R.R.
.R.R.R.R.RRRRRRR.R.R.
.R.R.R.R.........R.R.
.R.R.R.RRRRRRRRRRR.R.
.R.R.R.............R.
.R.R.RRRRRRRRRRRRRRRR
.R.R.................
.R.RRRRRRRRRRRRRRRRRR
.R.R.................
21
.................R.R.
RRRRRRRRRRRRRRRRRR.R.
.................R.R.
RRRRRRRRRRRRRRRR.R.R.
...............R.R.R.
...RRRRRRRRRRR.R.R.R.
.............R.R.R.R.
.....RRRRRRR.RRRRRRR.
.....R.....R.R.R.R.R.
.......RRR.R.R.R.R.R.
..........P..R.R.R.R.
.........R.RRR.R.R.R.
.........R.....R.R.R.
.......R.RRRRRRR.R.R.
.......R..R......R.R.
.......RRRRRRRRRRR.R.
.....R....R........R.
.....RRRRRRRRRRRRRRRR
.....................
...RRRRRRRRRRRRRRRRRR
.R.R.................
21
.................R.R.
RRRRRRRRRRRRRRRRRR.R.
................RR.R.
RRRRRRRRRRRRRRRRRR.R.
...............RRRRR.
...RRRRRRRRRRR.RRRRR.
.............R.RRR.R.
.....RRRRRRR.RRRRRRR.
.....R.....R.R.R.R.R.
.......RRR.R.R.R.R.R.
..........P..R.R.R.R.
.........R.RRR.R.R.R.
.RR......R.....R.R.R.
.RR....R.RRRRRRR.R.R.
.RR....R..R......R.R.
.RR....RRRRRRRRRRR.R.
.RR..R....R........R.
.....RRRRRRRRRRRRRRRR
.....RR..............
...RRRRRRRRRRRRRRRRRR
.R.R.................
21
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRRR..RRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRRR..RRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRR.RRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRR
RRRRRRRRR.RRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRR
R.R.RRRRR...R.R.RRRRR
RRRR......P......RRRR
RRRRR.R.R...RRRRR.R.R
RRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRR.RRRRRRRRR
RRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRR.RRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRR..RRRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
RRRRRRRRR..RRRRRRRRRR
RRRRRRRRRR.RRRRRRRRRR
0


## Output

At most 4 rose(s) trampled.
At most 2 rose(s) trampled.
At most 1 rose(s) trampled.
At most 2 rose(s) trampled.
At most 3 rose(s) trampled.
At most 3 rose(s) trampled.
At most 1 rose(s) trampled.
At most 0 rose(s) trampled.
At most 0 rose(s) trampled.
At most 3 rose(s) trampled.
At most 0 rose(s) trampled.
At most 1 rose(s) trampled.
At most 2 rose(s) trampled.
At most 0 rose(s) trampled.
At most 2 rose(s) trampled.
At most 3 rose(s) trampled.
At most 4 rose(s) trampled.