TopCoder problem "SwampyLands" used in TCHS SRM 24 (Division I Level Three)



Problem Statement

    

Some parts of farmer John's lands are swampy. These swampy regions are rectangles with horizontal and vertical sides. Your task is to find the total area of all the non-swampy regions that are surrounded completely by swampy lands. A non-swampy region is surrounded if it is not possible to leave the farm from anywhere on this region, without passing through some point of a swampy piece of land. The corners and edges of a swampy piece of land are considered to be swampy as well. See examples for further clarifications.

You are given a String[] swampy. The ith element of swampy is a space-delimited list of four integers in the form "x1 y1 x2 y2" (quotes for clarity only) where (x1, y1) and (x2, y2) are the opposite corners of the ith rectangular piece of swampy land. Return the total area of all the non-swampy regions that are surrounded by swampy lands.

 

Definition

    
Class:SwampyLands
Method:surroundedArea
Parameters:String[]
Returns:int
Method signature:int surroundedArea(String[] swampy)
(be sure your method is public)
    
 

Constraints

-swampy will contain between 1 and 50 elements, inclusive.
-Each element of swampy will be in the form "x1 y1 x2 y2" (quotes for clarity only) where x1, y1, x2 and y2 are integers between -20,000 and 20,000, inclusive, with no leading zeroes.
-In each element of swampy, x1 will be less than x2 and y1 will be less than y2.
 

Examples

0)
    
{"1 4 3 9", "1 2 9 4", "7 4 9 9", "3 9 9 11"}
Returns: 20
There are four pieces of swampy land here, as shown in the picture below. The brown rectangles are the swampy parts of farmer John's lands. The gray region is the only surrounded region, so we return its area.



1)
    
{"5 12 16 14", "4 5 7 13", "2 3 22 7",
 "3 9 22 10", "11 4 13 17", "16 2 20 14"}
Returns: 28
The layout of farmer John's lands is depicted below. In this case there are four surrounded regions with a total area of 28.



2)
    
{"8 7 11 14", "7 12 10 19", "2 14 9 17", "9 18 21 21",
 "6 11 18 13", "18 6 20 18", "9 4 21 7"}
Returns: 67
3)
    
{"1 4 3 9", "1 2 9 4", "7 4 9 9", "4 9 9 11"}
Returns: 0
4)
    
{"2 1 3 2", "1 2 2 3", "2 3 3 4", "3 2 4 3",
 "5 2 6 3", "6 1 7 2", "6 3 7 4", "7 2 8 3"}
Returns: 2

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10076&pm=7270

Writer:

_efer_

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Search