TopCoder problem "Shapes" used in TCHS SRM 40 (Division I Level Three)

Problem Statement

Your friend has set a challenge for you. He took a square piece of paper, on which was drawn a square grid parallel to the sides, and divided it up into 5 pieces by making cuts along the grid-lines. Your challenge is to reconstruct the original square from the pieces.

You are given an int L containing the length in grid units of the sides of the original square and 5 String[]s: s1, s2, s3, s4 and s5, each containing the details of the shape of one of the pieces of paper. Each character in each shape corresponds to a single square of the grid and will be a '#' if the square is present and a '.' if not. The shapes are given to you in the same orientation that they were in as part of the original square (i.e., they have not been rotated or turned over since they were cut out).

Return a String[] containing the reconstructed square. The return value should contain L Strings of length L. Character j of element i of the return value should be a digit containing the number of the shape (i.e., the digit in the supplied variable name) that the grid-square at position (i, j) was a part of. If there are multiple solutions, return the one that comes first lexicographically. The lexicographically earlier of two String[]s is the one with the lexicographically earlier String in the first position at which they differ. If there is no valid way of reconstructing the square, then your friend must be cheating and you should return a String[] containing a single element, "CHEAT" (quotes for clarity).

The shapes must not overlap in the reconstructed square or extend outside its boundary.

Definition

Class:	Shapes
Method:	reconstructSquare
Parameters:	int, String[], String[], String[], String[], String[]
Returns:	String[]
Method signature:	String[] reconstructSquare(int L, String[] s1, String[] s2, String[] s3, String[] s4, String[] s5)
(be sure your method is public)

Constraints

L will be between 3 and 10, inclusive.

s1, s2, s3, s4 and s5 will each contain between 1 and L elements, inclusive.

Each element of s1, s2, s3, s4 and s5 will contain between 1 and L characters, inclusive.

Within each of s1, s2, s3, s4 and s5, every element will contain the same number of characters.

Each character in s1, s2, s3, s4 and s5 will be either a '#' or a '.'.

The first and last rows of s1, s2, s3, s4 and s5 will each contain at least 1 '#' character.

The first and last columns of s1, s2, s3, s4 and s5 will each contain at least 1 '#' character.

The '#' characters in each of s1, s2, s3, s4 and s5 will be connected.

Examples

{"#####"}

{"#####"}

{"#####"}

{"#####"}

{"#####"}

Returns: {"11111", "22222", "33333", "44444", "55555" }

Here your friend cut the paper into strips. There are many ways that the square could be reconstructed, so we choose the lexicographically earliest.

{"##"
,"##"}

{"########"
,"#......#"
,"#......#"
,"#......#"
,"#......#"
,"#......#"
,"#......#"
,"########"}

{"######"
,"#....#"
,"#....#"
,"#....#"
,"#....#"
,"######"}

{"####"
,"#..#"
,"#..#"
,"####"}

{"##########"
,"#........#"
,"#........#"
,"#........#"
,"#........#"
,"#........#"
,"#........#"
,"#........#"
,"#........#"
,"##########"}

Returns: 
{"5555555555",
"5222222225",
"5233333325",
"5234444325",
"5234114325",
"5234114325",
"5234444325",
"5233333325",
"5222222225",
"5555555555" }

This time your friend cut up the paper into rings.

{"#....."
,"######"
,"######"}

{".###"
,"####"
,"####"}

{"###.."
,"###.."
,"##..."
,"####."
,"#####"
,".####"}

{".#"
,".#"
,".#"
,"##"
,"##"}

{"####."
,"#####"
,"..###"}

Returns: {"CHEAT" }

These shapes cannot form a square.

{"#####"}

{"#####"}

{"#####","#####"}

{"#####"}

{"#####"}

Returns: {"CHEAT" }

{"##",".#"}

{".#","##","##","##"}

{"##.","###","###","##."}

{"...#..","..##..","######","######"}

{"#"}

Returns: {"331152", "333122", "333422", "334422", "444444", "444444" }

{"##.....",".#####.","....###"}

{"#....","####.","####.","####.","#####","..###","..###"}

{".###","..##","...#","####","####",".###",".###",".###"}

{"##","##"}

{"###"}

Returns: 
{"11555333",
"21111133",
"22221113",
"22223333",
"22223333",
"22222333",
"44222333",
"44222333" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10784&pm=7791

Writer:

StevieT

Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Problem categories:

Brute Force, Recursion, String Parsing