PROBLEM STATEMENT
There are 7 tetronimos:
A B C D E FF G
A B C DD EE FF GG
A BB CC D E G
A
How many different ways can you completely cover a given shape by placing
tetronimos so that no pieces overlap?
Each tetronimo can be used at most once, and can be moved or rotated as you
want, but not flipped.
The input will be a String[] with 4 elements and 6 characters in each element,
and will only contain '.'s and 'X's. The shape is defined by the 'X's.
Example 1:
The String[] {"......","..X...",".XXX..","XXXX.."} represents the following
shape:
......
..X...
.XXX..
XXXX..
This has 2 solutions:
...... ......
..E... ..G...
.GEE.. and .GGG..
GGGE.. AAAA..
so the method would return 2.
Example 2:
The String[] {"XX....","XX....","XX....","XX...."} represents the following
shape:
XX....
XX....
XX....
XX....
This has no solutions.
Note that you cannot flip 'B' vertically and solve it as:
BB....
BC....
BC....
CC....
Pieces may only be rotated 0, 90, 180, or 270 degrees - they may NOT be flipped.
the method would return 0.
Example 3:
The String[] {"XXXXXX", "XXXXXX", "XXXXXX", "XXXXXX"} represents the following
shape:
XXXXXX
XXXXXX
XXXXXX
XXXXXX
There are 2 solutions:
BBBCCC
BDFFEC
DDFFEE
DAAAAE
and
EAAAAD
EEFFDD
CEFFDB
CCCBBB
Note that these are 180 degree rotations of each other.
Even though they use the same pieces in similar positions, they are different
configurations and both are valid.
the method would return 2.
DEFINITION
Class: Tetronimo
Method: numWays
Parameters: String[]
Returns: int
Method signature (be sure your method is public): int numWays(String[] shape);
NOTES
- if there is at least one 'X', but no way to make the shape with the
tetronimos, return 0.
- if the shape is empty (i.e. no 'X's), return 1.
- use each piece at most once.
- rotation is allowed but flips (mirroring over an axis) are not.
- rotations will be 0, 90, 180, or 270 degrees only. No pieces may be placed
diagonally.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- shape will have exactly 4 elements
- each element of shape will contain exactly 6 characters
- each element of shape will contain only the characters '.' and 'X'
EXAMPLES
(1)
shape = {"......",
"..X...",
".XXX..",
"XXXX.."}
the method would return 2
(2)
shape = {"..X...",
"..X...",
"..X...",
"..X..."}
the method would return 1
(3)
shape = {"......",
"......",
"......",
"......"}
the method would return 1
(4)
shape = {"XXXXX.",
"XXXXX.",
"XXXXX.",
"XXXXX."}
the method would return 8
(5)
shape = {"XXXXX.",
"X...X.",
"X...X.",
"XXXXX."}
the method would return 0
(6)
shape = {"XXXX..",
".XXXX.",
".XXXX.",
".XXXX."}
the method would return 12
(7)
shape = {"XXXXXX",
"XXXXXX",
"XXXXXX",
"XXXXXX"}
the method would return 2