BrickPuzzle

SRM 451 · 2009-10-20 · by vexorian

SRM 451 · 2009-10-20 · by vexorian · Dynamic Programming, Math, Search

Show categories

Class Name: BrickPuzzle

Return Type: int

Method Name: leastShapes

Arg Types: (vector<string>)

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.

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

{"..X....",
 "..XXXXX"}
Returns: 2

{".X",
 "..",
 "X."}
Returns: -1

Note that the pieces cannot be rotated.

{"..XX....",
 "....X..X",
 "XX..XXXX"}
Returns: 4

{"X..XXXX",
 "X.....X",
 "....XX.",
 "X......"}
Returns: 5

This is the example from the statement.

{"......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................",
 "......................"}
Returns: 121

143)

{
"..X..X.X..",
".X..X.X...",
"XX...X....",
"...X....X.",
".X....X.X.",
"...X......",
"X.........",
"...X......",
"X...X.X...",
"..XX..XX.."
}
Returns: 23

only 2 possible solutions in this case

144)

{
"X.XX.XXX.X",
"XX.XXX..X.",
"XXXX.XXXX.",
".XX..XX.X.",
"...XXXXX.X",
"X..X...XXX",
".XX..XXXXX",
"X.XXX.X...",
"X.X.....XX",
"..XX.....X"
}
Returns: 16

1 solution

145)

{
"X..XX..X..X.XXX",
".XX.XXX...X.XX.",
".XX.X...XX..XXX",
"...XX.XX...X..X",
"...XX..XXXXXXX.",
".X...XXX.....X.",
".XX........XX..",
"...XXXXXX..X.X.",
"..X.....XX...X.",
"XXXX..XXXXXXX..",
".XXXX.X.X..X.X.",
"...XX.X.X..XXX.",
".XX.XX..X..X.X.",
".XXXXX..XX...X.",
".XXX.XX.X..XX.."
}
Returns: 40

2 solutions

146)

{
".X.X.X.X.X.XXXX.X.",
"XX..X..XX....XXXX.",
"X.X.X.X........XX.",
"XXXXX....X...XX...",
"X..X..X.XX...X..XX",
".X.XX..X..XX...XX.",
"...X.X..XX..X...XX",
".X.X.X.X.XXXX.X...",
".X.XXXXXXX..XX..XX",
".XXX..XX....XXXXX.",
".XX.XXX.X.X.X.XXX.",
"XXX.X.X.XXX.X.X.X.",
".XXXX..XXX..XXXX.X",
"X..XX.X..X..X...XX",
".XX.XXX..X..XXX..X",
"X.X.XXX..X..XXX.X.",
"X.XXXXX.X.X.X.X.X.",
".XX.XX....X....XX."
}
Returns: 57

2 solutions

147)

{
"X..X......",
".XX..X..X.",
"....X.....",
"X.X.......",
".....X....",
".X.X......",
"...X.X.X..",
".X.X..XX..",
".X.X.X.X..",
"......XX.."
}
Returns: 23

1 solution

148)

{
".......XXX..",
"...X.X...X.X",
".XXXX.......",
"..XXX..XX..X",
".X.......XXX",
"........XX..",
"X.....X.X.X.",
"....XX......",
"...X.....XXX",
"XX.X..X...X.",
".......X....",
".........X.."
}
Returns: 31

1 solution

149)

{
"..X..X........",
"......X...X...",
".X..X....X..X.",
"...X.....X....",
"...X.X.......X",
"X.....X...X...",
"..XX..........",
".XX..X....XX..",
"X..X..........",
".XXXX.........",
"...........X.X",
"......XX......",
"X....XX.X.....",
".X....XX....X."
}
Returns: 44

3 solutions

150)

{
"XXXXX.X..X..XXX......",
".XXX.X...X.X.X.X.X.X.",
"X..XXXXXXX....XX.XXX.",
".XX....X..XX..XX.X.X.",
".XX..X............XXX",
"XXX.......XX..XX.X.X.",
"...X.X.XXXXXXX...X.X.",
"X..XXXXX.X..XX.X.XXX.",
".XXX.XX.X.....X.XXXXX",
"..XXXX.....X.X...X...",
".X.XX....XX..XX.XX..X",
"XXX..X....XXX..X....X",
".XX.X..X..X.XXX..X.X.",
"XX..X....X.XXXXXXXXXX",
".X.XX.XXXXX..X.X..XX.",
"X...X.XX.XX..X.X...XX",
"X.X.X....XXXXX.X.X.X.",
"XXX.XXXXX.XXXXX....X.",
".X.XX...XXXXX.XX..XXX",
".X.XXX.X.XXXXX..XX...",
"XX..X..XXX..X.XX.X.X."
}
Returns: 74

4 solutions

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

Coding Area

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