1721 . Pizza 514
TopCoder
Description
The PDF version of this problem can be downloaded here.
The Pizza Festival is coming. Everyone in the Pizza Kingdom is excited for this once-
in-a-decade event. You have decided to present a jumbo pizza to God to thank him for
everything and to honor his glory.
The jumbo pizza that you want to present is n x m in size and consists of jewelries
and three kinds of small pizzas: Pizza-5, Pizza-1, and Pizza-4. Pizza-5 is 1 x 1 in
size, with ham and pineapple toppings. Pizza-1 is 1 x 2 in size, with tomato, sliced
mozzarella, and basil leaves toppings. Pizza-4 is 2 x 2 in size, L-shape, with sausage
and olives toppings. You may rotate the small pizzas before putting into the jumbo
pizza.
The priest has told you the pattern to place the jewelries in the jumbo pizza to bless
your fortune. He also gave you a lucky sequence of 5, 1 and 4 to place the small pizzas.
Following his suggestion, you would like to place the small pizzas in a way that when
recording the pizza number from top to bottom and from left to right, the sequence is
exactly the same as the lucky sequence. Every small pizza has to be placed completely
inside the jumbo pizza, and there must be no empty space in the jumbo pizza. How
many ways are there to place the small pizzas?
Input Format
The first line of the input le contains an integer T (1 ≤ T ≤ 45) indicating the number
of test cases.
Each test case starts with a line containing three integers, n, m, and k (1 ≤ n,m ≤ 18, 1 ≤ k ≤ 350), denoting the size of the jumbo pizza and the number of small pizzas
in the jumbo pizza. The next line contains k characters (5, 1, or 4) representing the
lucky sequence. The following n lines presents the pattern of the jewelries. Each line
contains m characters, '.' or '#'. All '#' will be lled by jewelries. You have to cover all '.'
with small pizzas.
Output Format
For each test case please output a line containing the number of ways to place the small
pizzas satisfying all the constraints. Since the number may be large, please output the
number modulo 0x514b122a.
Sample Input 1
3 4 4 6 514111 ...# #... ...# ...# 3 5 6 111514 ..... ..... #..## 4 3 5 11154 ... ... #.. #..
Sample Output 1
5 1 4
Hints
The solutions to the rst test case are shown below.
Problem Source
Migrated from old NTUJ.
tmt514
Subtasks
| No. | Testdata Range | Score |
|---|