Problem G
Colored Tiles
Input: Standard Input
Output: Standard Output
Tanzibal has got 7
types of tiles with her and there are infinite supplies of each. The following
diagram depicts the shape and color of each tile.
|
|
|
|
|
|
|
Tile #1 Color: Red |
Tile #2 Color: Grey |
Tile #3 Color: Blue |
Tile #4 Color: Green |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tile #5 Color: Brown |
Tile #6 Color: Pink |
Tile #7 Color: Black |
|
All
the tiles are different in shape and color. For those who are color blind
and/or using a black-white printed version of the above figure, the color of
each tile is given below its corresponding figure.
Tiles numbered 1-4
are L shaped. Tile 5 has a dimension of 2 x 1. Tile 6 has a dimension of 1 x 2.
Tile 7 has a dimension of 1 x 1.
Tanzibal
has a board of size N x M. She would like to cover the board
completely with the tiles at her disposal. The rules of tilings goes like this:
·
The
tiles can’t be rotated.
·
Some
of the cells of the board are broken and she can’t place any tile on top of
those cells.
·
Some
of the cells of the board are special. Each special cell is marked with a
single color. The color of each special cell will be from the set {Red, Grey,
Blue, Green, Brown, Pink & Black} and will be denoted by {R, G, B, N, W, P,
L} respectively, for the sake of brevity. Tanzibal has to make sure that those
cells are covered by a tile with the same color as that of the cell.
Can you help Tanzibal by finding out the number of
different ways she can tile the whole board? Two configurations are different
if there is at least one cell that is tiled with a different color.
Input
The first line of input is an integer T(T<50)
that indicates the number of test cases. Each case starts with two integers N(0<N<9)
and M(0<M<20) that represents the dimension of the board.
Each of the next N lines will contain M characters each. Broken
cells will be represented using ‘#’, empty cells will be represented
using ‘.’ and the special cells will be given by one of {R, G, B, N, W,
P, L}.
Output
For each case, output the case number
followed by the total number of configurations. Since the total number of ways
can be very big, output the result modulo 50431.
Sample Input Output
for Sample Input
|
3 3 3 ... ... ... 1 4 ..#. 2 2 .. N. |
Case
1: 369 Case 2: 2 Case
3: 0 |
Problem
Setter: Sohel Hafiz
Special
Thanks: Md. Arifuzzaman Arif