Connection Status:
Competition Arena > AreaSplit

AreaSplit

TCO05 Semi 2 · 2005-08-16 · by gepa

TCO05 Semi 2 · 2005-08-16 · by gepa · Brute Force, Simple Search, Iteration
Class Name: AreaSplit
Return Type: String[]
Method Name: halfPattern
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Some square tiles have been selected from a N x M chessboard, building a pattern (not necessarily connected). You have the task of coloring some of the selected tiles red and all of the others blue so that the pattern composed by the blue tiles is a shifted copy of the pattern composed by the red tiles. One example is shown in the figure below (the white tiles in the left image are the selected tiles, which are colored in the right image).

You will be given a String[] board containing N elements, each of them M characters long, with a character '#' indicating that the tile in the corresponding position belongs to the selected tiles (i.e., to be colored, the white tiles in the example above), a character '.' indicating a tile that shall be ignored (the gray tiles in the example above). Return a String[] representing the red pattern, after cropping the image to the smallest rectangle that contains all the red tiles. Use the character '#' to denote tiles painted in red, '.' to denote other tiles. If there are several ways to color the tiles so that two equal patterns are created (one in red, one in blue), use the solution in which the red pattern has the smallest width (horizontal distance from the leftmost red tile to the rightmost red tile). If there are several ways with the smallest width, use the solution among them with the smallest height (vertical distance from the uppermost red tile to the lowermost red tile). If there is still a tie, use the one among the tied ones that comes first lexicographically after you concatenate the Strings representing the solution ('#' comes before '.'). If there is no solution, return an empty String[].

Notes

  • Since the red and blue patterns are translated copies of the same pattern, the returned value would be the same if we asked for the blue pattern (since we crop the returned value to the width/height of the resulting pattern).
  • All elements of the returned String[] shall have the same length (the width of the red pattern).

Constraints

  • board will contain between 1 and 50 elements, inclusive.
  • Each element of board will have between 1 and 50 characters, inclusive.
  • Each character of each element of board will be either '#' or '.'.
  • There will be at least one '#' character in at least one element of board.
Examples
0)
{".........",
 ".##......",
 "..#.##...",
 ".#####...",
 ".#######.",
 ".#..###..",
 "....#....",
 "........."}
Returns: {"##..", ".#..", "####", "###.", "#..." }

The example from the problem statement.

1)
{"##",
 "##"}
Returns: {"#", "#" }

Here, two different half-patterns are possible: the horizontal {"##"} (width 2, height 1) and the vertical {"#", "#"} (width 1, height 2). We return the one with the smallest width.

2)
{".#..#",
 "##.##"}
Returns: {".#", "##" }

Note that the pattern need not be connected.

3)
{".#.##",
 "####.",
 "#...."}
Returns: {"#.##", "#..." }

Even if the pattern is connected, the solution may not be connected.

4)
{".###.",
 "##.#.",
 "..###"}
Returns: { }

We can not split this pattern into two equal patterns.

12)
{".#.",
 "#.#",
 ".#."}
Returns: {"#.", ".#" }

Here, both {"#.", ".#"} and {".#", "#."} are possible solutions. We have to return the first of these solutions (if we concatenate the two Strings of that solution we get "#..#" which comes lexicographically before ".##.", the concatenation of the Strings of the second solution).

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

Coding Area

Language: C++17 · define a public class AreaSplit with a public method vector<string> halfPattern(vector<string> board) · 87 test cases · 2 s / 256 MB per case

Submitting as anonymous