TopCoder problem "WaterPressure" used in TCO '03 Round 3 (Division I Level Two)



Problem Statement

    You have been given a String[] layout containing a map of an underground cavern. The jth character of the ith element of layout will correspond to row i column j in the map. Water has begun flowing in at the upper lefthand corner (row 0, column 0), and will soon makes its way throughout the cavern. Each character in layout will either be a digit (0-9) or 'X' (except for the upper lefthand corner, which will always be '.', and can be thought of as water). An 'X' means that water will never penetrate the solid rock present in that area. A digit describes how much water pressure is required to penetrate that area. The water will travel according to the following rules:
  • 1) Each second, beginning with second 0, the total amount of water increases by 1 in the squares where water has reached.
  • 2) The total water pressure is equal to the total amount of water divided by the total number of squares the water has reached. This need not be an integral amount.
  • 3) At the end of each second, after the total amount of water has been incremented, each square adjacent to the water (not diagonally) is checked for strength. Every adjacent square, whose digit value is strictly smaller than the total water pressure, will become covered with water.
Above, the total amount of water, and total amount of water pressure are values corresponding to the map as a whole, and not individual squares. Note that the water will never leave the map. When calculating which squares become covered during a given second, all squares adjacent to water are considered simultaneously. In other words, one square getting flooded will not then change the pressure, and prevent another square from getting flooded that same second. In addition, only squares directly adjacent to the water may be flooded during any second. Before second 0 occurs, the square in the upperleft hand corner is already flooded, and the total water is 1. This implies, after the increment occurs during second 0, the total water will be 2, and the total water pressure will be 2. Your method will return the second during which the last square containing a digit is flooded. If this will never occur, return -1.
 

Definition

    
Class:WaterPressure
Method:howLong
Parameters:String[]
Returns:int
Method signature:int howLong(String[] layout)
(be sure your method is public)
    
 

Notes

-Total water pressure need not be an integer.
 

Constraints

-layout will contain between 1 and 50 elements inclusive.
-Each element of layout will contain between 1 and 50 characters inclusive.
-Each element of layout will contain the same number of characters.
-The 0th character in the 0th element of layout will be (quotes for clarity) '.' . Every other character in layout will be a digit ('0'-'9') or 'X'.
-layout will contain at least one digit.
 

Examples

0)
    
{
".0",
"0X"}
Returns: 0
During second 0 the total water will be incremented to 2. Thus, the total pressure is 2. This is clearly greater than 0, so both '0' squares will be flooded. Since no digit squares remain unflooded, your method returns 0.
1)
    
{
".0",
"00"}
Returns: 1
Once second 0 is complete:

Total water = 2

Total filled = 3

Total pressure = 2/3

Current layout ('.' denotes flooded):
"..
 .0"
During second 1 the final digit containing square is flooded.
2)
    
{
".5",
"44"}
Returns: 14
3)
    
{".23456789"}
Returns: 71
4)
    
{
".X0",
"X00"}
Returns: -1
The 'X' blocks the digit containing squares. Since the water can never reach the '0's, your method returns -1.
5)
    
{
".85773817518159249980260123498780838839X6384717463",
"242194445126058X5X93973323184X3X2747X842171X286218",
"598X67822897X5X61920060240170X31256497102692827551",
"54X36408X2548801X136636X63X9233X5949346X2274580162",
"5108021354X77X4477509918743895XXX159760734682X9115",
"50675439X0922X79916947371X01901217614357X0397201X3",
"27186118593416001273104X29X76977141883369859598888",
"80914X110594111X436841522027X668157791200228638293",
"940105447111X78X25011577574123524X04XXX51614492051",
"8804363635177X8246382862576X601870X74X139993345821",
"X48877009143171494700XX3X16138573259477742520850X9",
"1612588394913980186365912312794180464979928X986475",
"595353627322252222412X883094875X522435782213598237",
"17391130462739808923430X258255508957X4539278411137",
"161196X087X1959308152303433460329X6588920868810551",
"5X05897317154867X286045721X246725361349XX31742455X",
"X6356984801056259X735653998127X568670314628X485224",
"9320088X74859675156365X779X1X326767X79844419358X2X",
"501055497X39933X951356690965X4X0844917186293X57985",
"33413302X1903266448066612423X8038586XX5638903X7517",
"2976X251488X07X87464805678010167X32X54795816434863",
"18X8XX869283086X940798825X85739462998X3X3834428505",
"2555044879X7309586526260751345349591446476X7010X13",
"3233684019X20X770513442033X6950060849326X814045XX1",
"7378853595549545X9334157X55988471X21X3295375894550",
"7X9037779323X31807337002826035684828290777975X01X4",
"88X7X979X7X39506209854X7415XX8999X2253016X25035787",
"7683015X17268X16694392X6X101441658747937X198485622",
"1624X697868860600X030X577356X121482831384673XX7334",
"4662712538X13X4168850436576272047034855X5933218977",
"363X88X712383950892X775895613479X5287X01182X614158",
"0944515500373672425X6066X2108X3247524582717066X178",
"637664873632165059897471275828595X6527260271X84X40",
"305512X0X86260235207058X57705027964497905850617962",
"935138076111582XX0369X62229X178X921961753325422758",
"9987594X029815548549X858304X3181752985X5927X716348",
"631347X74X23510X703201850X965X8803X5794257X7X32012",
"597X2244071123X41X44196191328874040522673675346X00",
"9501X65935X9375252X55199X261467XXX8118871789524X62",
"732087503876417410X23X95740041509X58104X7543083124",
"175978X56605686460653815X08585X89XX137855313405573",
"51593131735080324921X2253417397314274XX231X5293926",
"XX778362173333574X333953005142250501X79X21757X1264",
"57350X7252505123850942501148X63526X106805090642546",
"2331X884X085X068X18X612328531670865X09525594XX98X6",
"6935X60327121102150643X49857600X77316813X362130791",
"331X29776535751774789772426596X1961969905180339X10",
"358X6622772195016X79558982X1024678439091439835013X",
"305362575995391477X2744272460098891730534152558XX1",
"28318306546365480X775289935065X4X48610794894231736"}
Returns: 18566

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4704&pm=1907

Writer:

brett1479

Testers:

Problem categories:

Simulation