TopCoder problem "PatternCutting" used in SRM 241 (Division I Level Three)



Problem Statement

    

You have a rectangular sheet of paper, from which you wish to cut a pattern. The pattern is a figure composed of unit squares. You wish to cut out as many instances of the pattern as possible from the sheet of paper. The pattern may be cut out exactly as is, or may be rotated 90 or 180 degrees (in either direction).

You are given ints height and width, describing the size of the sheet of paper, and a String[] pattern that defines the pattern you want to cut out. pattern is composed of 'X' characters and period ('.') characters, where 'X' is part of the pattern, and '.' is not. The following respresents the 7 valid patterns with 4 'X's (ignoring rotations of the same pattern):

{"XXXX"}

{"XXX",
 "X.."}

{"XXX",
 "..X"}

{"XXX",
 ".X."}

{"XX.",
 ".XX"}

{"X.",
 "XX",
 ".X"}

{"XX",
 "XX"}

So, for the T-shaped pattern, from a 4 x 5 sheet of paper, you could cut out the pattern four times. One way would be like this:

A.BBB
AA.BC
AD.CC
DDD.C

You are to return an int indicating the maximum number of times the given pattern can be cut from the sheet of paper.

 

Definition

    
Class:PatternCutting
Method:getMax
Parameters:int, int, String[]
Returns:int
Method signature:int getMax(int width, int height, String[] pattern)
(be sure your method is public)
    
 

Constraints

-height and width will be between 1 and 6, inclusive.
-pattern will contain between 1 and 6 elements, inclusive.
-Each element of pattern will contain between 1 and 6 characters, inclusive.
-Each element of pattern will contain the same number of characters.
-Each character of each element of pattern will be 'X' or '.'.
-The first character of the first element of pattern will be 'X'.
-Each block of the pattern will be connected (horizontally or vertically) to the rest of the pattern.
-The pattern will not contain any empty rows or columns (it will not be "padded").
 

Examples

0)
    
4
5
{"XXX",
 ".X."}
Returns: 4
As in the problem statement, you can cut out the T pattern four times.
1)
    
6
5
{"XX",
 "XX"}
Returns: 6
Although there are 30 unit squares in the paper and only four used by our pattern, we are going to waste at least 6 squares from which we cannot cut another pattern. We can cut out no more than 6 of the pattern.
2)
    
4
3
{"XXXXX",
 "XX..."}
Returns: 0
Here, our pattern is simply too large to cut from the paper, so we can't cut it out at all.
3)
    
6
6
{"XXX",
 "X.X",
 "XXX"}
Returns: 4

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7216&pm=4425

Writer:

timmac

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Geometry, Search