TopCoder problem "LawnMower" used in TCO04 Round 3 (Division I Level Three)

Problem Statement

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 steered either 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) and back(B).

   - 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 before 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 width of my lawn, n, and int[]s 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.

Definition

Class:	LawnMower
Method:	trimNeeded
Parameters:	int, int[], int[]
Returns:	int
Method signature:	int trimNeeded(int n, int[] row, int[] col)
(be sure your method is public)

Constraints

n is between 2 and 12 inclusive.

row contains between 1 and 50 elements inclusive.

col contains the same number of elements as does row.

Each element of row is between 0 and n-1 inclusive.

Each element of col is between 0 and n-1 inclusive.

Examples

{0,1,0}

{0,2,0}

Returns: 6

   B S S -
   o - B o
   o - - o
   - o o -

The best place (there are other equally good places) for the shed is row 0, columns 1 and 2. The mower can just barely mow in a circle and get back to the shed. Each 'o' shows a cell that the lawn mower cuts. Note that there are only two bushes (one is repeated). Each '-' shows a grass cell that cannot be mowed.

{0}

{0}

Returns: 4

With no bushes in the way (we can't get the mower into the corner anyway) and a bigger yard, we can build the shed at row 0, columns 1 and 2, and cut everything except the 4 corners and the middle. Since one of those corners has a bush, that leaves 4 grass cells that must be trimmed by hand.

{3,3,3}

{4,4,4}

Returns: 5

There is just one (repeated) bush. We can build the shed on top of the bush at rows 3 and 4, column 4. We will then be able to mow everything except the four corners and the middle.

{0}

{0}

Returns: 6

This yard is just too small for the mower. We can build the shed on two grass cells and just leave the mower in the shed; that leaves the 9 cells containing 1 bush, 2 shed, and 6 grass, all of which must be trimmed by hand.

{11}

{11}

Returns: 3

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=926

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5880&pm=926

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , vorthys

Problem categories:

Brute Force, Graph Theory