PROBLEM STATEMENT
Three farmers, 'A', 'B', and 'C' who share a plot of land have recently had a
fight and want to put a fence up around their property. How much will it cost?
For this problem, 'square' means a character representing the ownership of a 1
meter by 1 meter area.
Each meter of fencing costs 1 and every section that is completely fenced off
needs a sign to show its ownership. Each sign costs 10.
There should be a fence between every pair of adjacent squares which are owned
by different farmers, and around the border of the entire plot.
The fences will divide the plot of land into non-overlapping 'sections'. A
section of land is connected land, all owned by the same farmer. Connected
means that you could move from each square in the section to every other square
in the section without crossing a fence, and only moving up, down, left or
right within the String[]. If the only way to get from one square to another
is by moving diagonally, they aren't connected and aren't in the same section,
as shown in the following example.
BA would represent 4 sections (the two 'A's are not connected)
AC
BA would represent 2 sections (the three 'A's are connected)
AA
There should be exactly one sign for each section.
Given a String[] which shows the ownership of the plot of land, return the
total cost of the project. Each character A, B, and C in the String[]
represents which farmer owns the square.
DEFINITION
Class: Farmers
Method: findCost
Parameters: String[]
Returns: int
Method signature (be sure your method is public): int findCost(String[] land);
NOTES
- each character in the String[] represents a 1 meter by 1 meter section of
land, i.e. to put a fence around a single character would cost 4.
- the fences will divide the plot of land into non-overlapping sections
- a single farmer may have multiple sections of land
- not all of the farmers have to appear in the input- sometimes only 1 or 2 of
the 3 will.
- the plot of land will always be rectangular
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- land will have between 1 and 50 elements, inclusive
- each element of land will have between 1 and 50 characters, inclusive
- each element of land will have the same length
- each element of land will consist of only of the uppercase letters 'A', 'B',
and 'C'
EXAMPLES
(1)
land = {"AAAAACCCC",
"AAAAACCCC"
"AAAAACCCC"
"BBBBBBBBB"
"BBBBBBBBB"};
You would need 28 meters of fencing around the border, 3 between A & C, 4
between C & B, and 5 between A & B for a total of 40.
You would also need a sign for each section (A,B,C) for a total of 30.
The method would return 70
(2)
land = {"AAAAAAAA",
"BBBBBBBA",
"CCCCCCBA",
"AAAAACBA"};
Here you'd need 24 meters around the border, 10 between A & B, 8 between B & C,
and 6 between C & A.
Total fencing: 48.
You'd also need 4 signs - one for B, one for C, and two for A (A has two
disconnected pieces of land).
48 + 4*10 = 88
The method would return 88
(3)
land = {"AABCBC",
"AACBCB",
"AABCAC"};
border: 18
internal: 20
signs: 13 sections = 130
The method would return 168
(4)
land = {"AABB"}
The method would return 31
(5)
land = {"A"}
The method would return 14