PROBLEM STATEMENT
You are given a pass to an exhibition. The exhibition floor is divided in
squares of equal size, with each square occupied by a single exhibition booth.
Each booth is labeled with a single letter 'A' through 'Z' designating its
type. You start your visit in some booth on the floor. Once you've started your
visit, the letter from the first booth is stamped on your pass. From that point
on, your visits are restricted to a group of booths that are (1) adjacent to
each other, and (2) labeled with the same letter as the initial booth you have
visited.
Given a floor map of the exhibition, determine the maximum number of distinct
booths you can visit based on the rules above.
DEFINITION
Class name: Exhibition
Method name: maxBooths
Parameters: String[]
Return type: int
Method signature (be sure your method is public): int maxBooths (String[]
floorMap);
The floorMap input parameter defines locations of the booths on the exhibition
floor. Elements of floorMap are strings of equal length, composed of characters
'A' through 'Z'. Each character corresponds to a booth, and designates its type.
Your method should return the maximum number of distinct booths that you can
visit starting anywhere on the floorMap, and visiting only the adjacent booths
of the same type. Two booths are adjacent when the squares in which they are
located share a single side. Note that two booths located in the squares that
share a single corner are *not* considered adjacent for the purposes of this
problem.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- floorMap has 1 to 50 entries, inclusive,
- All floorMap entries are of the same length,
- Each floorMap entry is 1 to 50 characters in length, inclusive,
- Each floorMap entry consists of upper-case characters 'A' through 'Z',
inclusive.
NOTE
EXAMPLES
1. floorMap= {
"ABA",
"BBB",
"ABA" }.
If you start your visit in any of the 'A' booths, that booth would be the only
one you are going to visit, because there are no other 'A' booths adjacent to
any of the 'A' booth on the floorMap. If you start your visit in any of the 'B'
booths, however, you will be able to visit all five 'B' booths, because they
are adjacent to each other. Your method, therefore, should return 5.
2. floorMap= {
"DDDEEEEEEEEDDD",
"DDDEEEEEEDDDDD",
"DDDEEEEEEEEDDD"}.
If you start your visit in any of the 'D' booths on the left, you would be able
to visit only 9 booths; if you start your visit in any of the 'D' booths on the
right, you would be able to visit 11 booths; if you start your visit in any of
the 'E' booths, you would be able to visit 22 booths. Therefore, your method
should return 22.
3. If floorMap= {
"ABBBBABBBBABBBABABABBBA",
"BBBABABABBBABBBBBABABBA",
"BBBBBBBBBAAAAAAABBBBBBB",
"AAAAAAAAAAAAABBBBBBBBBB",
"ABBBBBBBBBBBBBBBBBBBBBB",
"AABBBBBBBAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAA"
}, your method should return 61.
4. If floorMap= {"A"}, your method should return 1.