UVa 10798

From Algorithmist
Jump to navigation Jump to search

10798 - Be Wary of Roses[edit]

Summary[edit]

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

Explanation[edit]

Looking carefully at the search space, we note that for any , the most roses we need to trample is simply :

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 roses. Also, since , 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[edit]

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[edit]

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.