SandBag

PROBLEM STATEMENT

You are a natural disaster control engineer.  You know an area of land is about
to be flooded, and that there only is a single house in that area.  Your
workers are asking how to place sandbags in such a way as to stop this house
from being flooded using the fewest bags.  Worse, you only have 4 sandbags at
your disposal, which may not be enough.

The house lies on a square plot of land, no more than 8 meters by 8 meters in
size, which is surrounded by irrigation canals.  These canals will soon flood
to 3 meters above their normal flood levels.  You are given a map of the plot
of land - with the elevations of each 1 meter by 1 meter section relative to
normal flood level.

Create a class SandBag that contains the method minNumber, which takes two int
arguments that define the x and y positions of the house, and an argument map
which represents the map of the elevation of the land, and returns the minimum
number of sandbags needed to save the house, or -1 if it is impossible with
only 4 bags (or impossible altogether).  map will be a list of strings
containing only the characters [0-9], inclusive, such that the first character
of the first string represents the elevation of the top-left (x=0, y=0) 1 meter
by 1 meter cell, the last character of the first string will be the elevation
of the top right (x=max, y=0), the first character of the last string will be
for the bottom left, etc....


DEFINITION
Class: SandBag
Method: minNumber
Parameters: int, int, String[]
Returns: int
The method signature is as follows (be sure your method is public): int
minNumber(int x, int y, String[] map);


NOTES
- The water will come from the canals on all 4 sides just off the map.
- Sandbags will only be placed on an even 1 meter by 1 meter cell, and they
block water from traveling through that entire cell completely, regardless of
elevation.  Sandbags do not need to be stacked.
- Sandbags will NOT be placed on the same cell as the house.
- Water can travel from one cell to another in all of the 8 cardinal directions
(left, right, up, down, diagonal).
- Sandbags must be placed on the map, not off the map in a canal.
- Land elevated 3 meters or more stops the flow of the flood waters through
that cell, even if the land on the other side of it is at a lower elevation.
- If the house is on high ground that won't be flooded (3 or higher), this
house is in no danger and no sandbags are needed - return 0.
- If the house is not on high ground and is next to an irrigation canal (is on
an edge of the map), there is nothing that can be done to save the house -
return -1.
- If the house is not on high ground, but there is no path for the water to get
to the house that is not blocked by high ground, the house is in no danger and
no sandbags are needed - return 0.
- map need not be square (see the fourth example).


TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- The strings of map will contain only numerals ('0' - '9', inclusive).
- Each string of map will be the same length, which will be between 1 and 8
characters (inclusive).
- There will be between 1 and 8 strings (inclusive) in this map list.
- The given location of the house (x, y) will be a valid location on the map.


EXAMPLES

In each of these examples, quotes ('"'), commas (','), and parenthesis ('(' and
')') are included for clarity only.  They are never part of the input or output.

Example #1)
x = 3
y = 3
map = {"99999999", "90000009", "90000009", "90000009", "90000009", "90000009",
"90000009", "99999999"}
return 0
This house is already safe - it is surrounded by tall hills (the '9's are each
higher than 3 meters).  Here is the map (where "H" is the house's location):

	99999999
	90000009
	90000009
	900H0009
	90000009
	90000009
	90000009
	99999999


Example #2)
x = 1
y = 1
map = {"111", "111", "111"}
return -1
This house would take more than 4 bags to save.  It would have to be surrounded
by 8:

	111
	1H1
	111

Example #3)
x = 1
y = 1
map = {"33330", "30003", "30003", "30003", "33333"}
return 1
This house can be saved by simply putting a sandbag at position (4, 0), or at
(3, 1).  Either way, it would only take 1 bag to save this house.

Example #4)
x = 3
y = 0
map = {"0123210"}
return 0
This house is already on high ground.

Example #5)
x = 3
y = 3
map = {"0000", "0000", "0055", "0050", "0055"}
return -1
This house is right next to the canal and is not on high ground.  It can not be
saved.