I am considering buying a big new riding mower,
but I need to figure out how much hand trimming I will need to do. My lawn is a
square n x n grid of cells. Each cell is either grass, or it is a bush. It
is not possible to drive the mower over a bush.
The new mower occupies two adjacent cells. As it moves, the back end goes over
the same cell that the front end previously occupied, and the front end can be
to the next cell in the direction the mower is headed, or to one that is
45 degrees to the left or right.The following diagrams give examples showing the possible
cells (1, 2, or 3)
that the front of the mower could be steered to given the location of the front(F)
- 1 2 - - 1
- F 3 B F 2
B - - - - 3
I will build a shed for the
mower which will occupy two cells that are adjacent (either diagonally or orthogonally).
The shed is really just a roof over a concrete floor, so it is open on all sides and
the mower can freely pass through the shed going any direction. I am willing to destroy bushes to
make room for the shed. Each time I mow I must return the mower to the shed facing the same way as
I started mowing.
I don't mind going over the same places more than once,
but every cell containing grass that I can't mow will have to be trimmed by hand.
Create a class LawnMower that contains the method trimNeeded that takes the
my lawn, n, and ints row and col giving the locations of my bushes, and returns the
number of cells of grass that I will have to trim by hand (with my shed built
in the best location).
An element of row and the corresponding element of col give the location of a bush.
A bush may be listed more than once -- the repetitions can be ignored.