PROBLEM STATEMENT
A coal mine has collapsed, but we have a seismic picture of a vertical
cross-section that shows the locations of all the pockets that might contain
workers. 'X' indicates a section of rock, and '-' indicates airspace. We can
drill shafts vertically from the ground to a pocket, or from an already-reached
pocket to another pocket. It takes one hour to drill through each section of
rock. Create a class Rescue that contains a method howMany that takes a
String[] representing a map of the mine as input and returns how many hours it
will take to reach all the pockets, using an optimal rescue plan.
Example:
Mine Rescue Plan
XXXXXXXXXXXX-XXXX--- XXXX|XXXXXXX-XXXX---
XXXX-XXXXX--------XX XXXX-XXXXX--------XX
XXXXXXXXXXXXXXX--XXX XXXXXXXXXXXXXXX--XXX
XXX-XXXX----------XX XXX-XXXX----------XX
---XX---XXXXXXXXXXXX ---|X---XXXXXXX|XXXX
--------XXXXXXX--XXX --------XXXXXXX--XXX
---XXXXXXXXXXX--XXXX ---|XXXXXXXXXX--XXXX
XX-XXXXX------------ XX-|XXXX------------
XXX-------XXXXXXXXXX XXX-------XXXXXXXXXX
This mine has 4 separate air pockets (plus one which is exposed to the surface
already). An optimal rescue plan is shown with | denoting a section of rock
with a vertical shaft through it. One shaft goes from the exposed upper right
pocket to the one in the lower right. Then a shaft of length 2 connects to the
big pocket on the left. Notice that the vertical shaft in the next to bottom
row does not provide access to the pocket on its left -- the shaft needs to go
through two sections before it punches into the pocket above it. The remaining
two tiny pockets are reached by shafts of length one, one down from the
surface, and the other up from the left pocket. So the rescue will take 5 hours.
DEFINITION:
Class Name: Rescue
Method Name: howMany
Parameters: String[]
Returns: int
Method Signature (be sure your method is public): int howMany(String[] mine);
NOTES:
- mine provides a rectangular picture, with X denoting rock and - denoting
airspace.
- The first element of mine is the top level.
- Access within a pocket of airspace is limited to horizontal or vertical
adjacency.
- Each shaft requires len hours to drill, where len is the length of the shaft.
- Each shaft must be vertical, and provides no horizontal access to adjacent
pockets.
- We have only one drilling rig, so two shafts cannot be drilled concurrently.
- There is solid rock on the left, right, and below mine.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- mine has 1 to 50 elements (inclusive)
- all elements of mine have the same length
- each element of mine has length between 1 and 50 inclusive
- each String contains only the letters 'X' and '-'
Examples
1. {"XXXXX","-X--X"}: return 2
The rescue can be done with two shafts down from the surface, each of length 1.
2. {"XX","-X","XX","XX","--"}: return 3
There are two pockets. Reach the first by a shaft of length one down from the
surface, then reach the second with a shaft of length 2 from the
already-reached pocket.
3. {"XXX","XXX"}: return 0
The rescue is over before it begins.
4. {"-XXX","-XXX","-XX-","-XXX","----"}: return 1
5. {"X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-",
"-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X",
"X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-",
"-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X",
"X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-",
"-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X-X"}: return 100