TopCoder problem "FloodRelief" used in SRM 371 (Division II Level Three)



Problem Statement

    

Global warming has caused your home town to receive far more rain than usual, and it is in danger of becoming flooded. You have been put in charge of buying and installing pumps that will carry away the water. There is no limit on how much water a pump can handle, but they must be placed correctly so that all the water will flow into a pump, with no lakes or even puddles left over. The pumps are also expensive, so you must determine the minimum number that need to be bought.

You are given a String[] heights. This is a rectangular grid representing the height of each square meter of your town. It contains only lowercase letters ('a' - 'z'), with 'a' meaning low ground and 'z' meaning high ground. Water flows from a cell to every cell that shares an edge and is of equal or lower height. The town is surrounded by high mountains on all sides, so water cannot flow off the map. You must return the minimum number of pumps that can be placed to ensure that all rain will eventually flow to some pump.

 

Definition

    
Class:FloodRelief
Method:minimumPumps
Parameters:String[]
Returns:int
Method signature:int minimumPumps(String[] heights)
(be sure your method is public)
    
 

Constraints

-heights will contain between 1 and 50 elements, inclusive.
-Each element of heights will contain between 1 and 50 characters, inclusive.
-Each element of heights will contain the same number of characters.
-Each element of heights will contain only lowercase letters ('a' - 'z').
 

Examples

0)
    
{"ccccc",
 "cbbbc",
 "cbabc",
 "cbbbc",
 "ccccc"}
Returns: 1
A bowl-shaped area. A single pump in the center is sufficient.
1)
    
{"cbabcbabc",
 "cbabcbabc",
 "cbabcbabc",
 "cbabcbabc"}
Returns: 2
Two valleys separated by a ridge. Each valley needs a pump.
2)
    
{"ccccccccccc",
 "caaaaaaaaac",
 "caaaaaaaaac",
 "caazpppzaac",
 "caapdddpaac",
 "caapdddpaac",
 "caapdddpaac",
 "caazpppzaac",
 "caaaaaaaaac",
 "caaaaaaaaac",
 "ccccccccccc"}
Returns: 2
A castle with a central courtyard and a moat. One pump is needed for each.
3)
    
{"ab",
 "ba"}
Returns: 2
Water cannot flow diagonally.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10787&pm=8243

Writer:

bmerry

Testers:

PabloGilberto , Yarin , ivan_metelsky

Problem categories:

Graph Theory, Recursion