Connection Status:
Competition Arena > FloodRelief

FloodRelief

SRM 371 · 2007-10-13 · by bmerry

SRM 371 · 2007-10-13 · by bmerry · Graph Theory, Recursion
Class Name: FloodRelief
Return Type: int
Method Name: minimumPumps
Arg Types: (vector<string>)
Problem Statement

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.

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.

4)
{"zzzzzzzzzzzzzzzzz","ccccccczzzcccczzz","zzzczzzzzczzzzczz","zzzczzzzzczzzzzzz","zzzczzzzzczzzzzzz","zzzczzzzzczzzzczz","zzzczzzzzzcccczzz","zzzzzzzzzzzzzzzzz","zddddzddddzzdzzzd","zdzzdzdzzzdzddzdd","zdzzzzdzzzdzdzdzd","zddddzddddzzdzzzd","zzzzdzdzzzdzdzzzd","zdzzdzdzzzdzdzzzd","zddddzdzzzdzdzzzd"}
Returns: 13

Submissions are judged against all 36 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FloodRelief with a public method int minimumPumps(vector<string> heights) · 36 test cases · 2 s / 256 MB per case

Submitting as anonymous