TopCoder problem "PaperScraps" used in TCHS SRM 35 (Division I Level Three)

Problem Statement

You have two cutout pieces of paper, each of which may have one or more sections missing. You wish to arrange those two pieces, possibly overlapping, to cover the largest possible rectangular area. Each of the pieces may be rotated (in 90 degree increments), or flipped over.

You are given String[]s paper1 and paper2, where each character of each element is a '.' or an uppercase 'X' indicating whether or not the paper has a hole at that location, respectively.

Return the area of the largest rectangular region you can cover using the two pieces of paper.

Definition

Class:	PaperScraps
Method:	biggestRectangle
Parameters:	String[], String[]
Returns:	int
Method signature:	int biggestRectangle(String[] paper1, String[] paper2)
(be sure your method is public)

Constraints

paper1 will contain between 1 and 5 elements, inclusive.

Each element of paper1 will contain between 1 and 5 characters, inclusive.

Each element of paper1 will contain the same number of characters.

Each character of each element of paper1 will be uppercase 'X' or '.'.

paper2 will contain between 1 and 5 elements, inclusive.

Each element of paper2 will contain between 1 and 5 characters, inclusive.

Each element of paper2 will contain the same number of characters.

Each character of each element of paper2 will be uppercase 'X' or '.'.

Examples

{"X"}

{"X"}

Returns: 2

Put the two pieces of paper next to each other to make a 2x1 rectangle.

{"XX"}

{"X",
 "X"}

Returns: 4

Rotate one of the two papers, and then put them together to make a 2x2, or a 4x1 rectangle.

{"XXX",
 ".X."}

{"XX"}

Returns: 5

We can arrange the papers to get a 2x2:

XXX    XXX
YX.    .X.
Y..    .Y.
       .Y.

...but even better is to get a 5x1 like this:

XXXYY
.X.

{"XXX",
 "X.X",
 "XXX"}

{"XX",
 "X."}

Returns: 9

We can use the second piece to cover the hole in the first, and make a 3x3 rectangle. Note that the overlap is permitted.

{"XXXXX",
 "XXXX.",
 "XXX..",
 "XX...",
 "X...."}

{"XXXXX",
 "XXXX.",
 "XXX..",
 "XX...",
 "X...."}

Returns: 30

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10771&pm=8039

Writer:

timmac

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Brute Force