Connection Status:
Competition Arena > PatternCutting

PatternCutting

SRM 241 · 2005-05-04 · by erinn

SRM 241 · 2005-05-04 · by erinn · Geometry, Search
Class Name: PatternCutting
Return Type: int
Method Name: getMax
Arg Types: (int, int, vector<string>)
Problem Statement

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.

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
{"X"}
Returns: 36
4)
6
6
{"XX"}
Returns: 18

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

Coding Area

Language: C++17 · define a public class PatternCutting with a public method int getMax(int width, int height, vector<string> pattern) · 17 test cases · 2 s / 256 MB per case

Submitting as anonymous