TopCoder problem "BrickPuzzle" used in SRM 451 (Division I Level Three)



Problem Statement

    NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.



Howard Benson loves puzzles and is always eager to invent new ones. He has recently invented a new puzzle based on the old puzzles that involved placing various tetrominoes inside a rectangle. For this puzzle, Howard picked four kinds of tetrominoes and made pieces with their shapes. The player can use as many pieces of each kind as necessary. The pieces he made available are shown in the following image:







Another component of the puzzle is the board, which is a square grid composed of white and black cells. The objective of the game is to cover all the white cells by placing a minimum number of pieces on the board. There are many rules regarding the placement of the pieces:



  • The pieces may not overlap.
  • Every piece must lie completely inside the board.
  • The pieces must be aligned to the grid.
  • The orientation of each piece must be the same as the orientation in the picture above.
  • Black cells in the board may be covered if necessary.




For example, the following picture shows a board configuration and a solution using a minimum number of pieces:







You are given the board as a String[] board. The j-th character of the i-th element of board is 'X' if the cell at column j, row i is black and '.' if the cell is white. Return the minimum number of shapes that are required to cover all the white cells by following the aforementioned rules. If it is impossible to cover all the white cells following the rules, return -1.



 

Definition

    
Class:BrickPuzzle
Method:leastShapes
Parameters:String[]
Returns:int
Method signature:int leastShapes(String[] board)
(be sure your method is public)
    
 

Constraints

-board will contain between 1 and 22 elements, inclusive.
-Each element of board will contain between 1 and 22 characters, inclusive.
-All elements of board will contain the same number of characters.
-Each element of board will contain only the characters '.' and uppercase 'X'.
 

Examples

0)
    
{"..X....",
 "..XXXXX"}
Returns: 2
1)
    
{".X",
 "..",
 "X."}
Returns: -1
Note that the pieces cannot be rotated.
2)
    
{"..XX....",
 "....X..X",
 "XX..XXXX"}
Returns: 4
3)
    
{"X..XXXX",
 "X.....X",
 "....XX.",
 "X......"}
Returns: 5
This is the example from the statement.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13905&pm=10524

Writer:

vexorian

Testers:

PabloGilberto , bmerry , ivan_metelsky

Problem categories:

Dynamic Programming, Math, Search