# 2000 ACM South Central Regional Programming Contest

## Louisiana State University

## Problem #8: Tetris

## Introduction

Uncle Jacques has purchased some
colorful floor panels for the dance floor of his club. Every Friday
his employees will rearrange the panels so that the disco dance floor
will have a new and exciting look. He has purchased a large supply
of panels with seven different shapes. Each panel consists of four 1
foot squares as depicted below:

_
_ _ _ _ _ | |
| | | | _| | | |_ | |_ _ _ | |
| |_ _| | | _| |_ | | _| | | | |
|_ _| |_ _| |_| |_| |_| |_ _| |_|
1 2 3 4 5 6 7

Uncle Jacques needs to know if his
dance floor can be completely covered using these panels. He also
needs to know how many different patterns his employees can create on
the dance floor. The panels can be rotated in 90-degree increments,
they cannot overlap, they cannot extend past the edge of the dance
floor, and they must cover the dance floor completely.

Your first job is to determine whether
the dance floor can be completely covered. Your second job is to
determine the number of different patterns that can be created by
rearranging the panels. Patterns are considered distinct if the
borders between panels are different. For example, for a 4 foot by 2
foot dance floor, there are 4 distinct patterns:

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| |_ _ | | _ _| | |_ _ _ _| | | |
|_ _ _|_| |_|_ _ _| |_ _ _ _| |_ _|_ _|

Rotations of patterns are also
considered distinct. For example, the following four patterns are
distinct:

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _|_ | | _ _| | |_ _ _ _| | |_ _ |
| | | | |_| | | | | | | | | |_|
|_|_ _|_| | |_ _| | | |_ _| | | |_ _| |
|_ _ _ _| |_ _ _|_| |_ _|_ _| |_|_ _ _|

## Input

Your program must accept the length and
width of the dance floor in feet. There can be any number of dance
floor measurements in the input. The dance floor will not be larger
than 36 square feet.

## Output

There will only be one line of output
for each set or measurements. Your program must return the number of
distinct patterns, which completely cover the dance floor. If the
floor cannot be completely covered, your program must return zero.

## Sample Input

2 4
3 3
3 4
4 4

## Sample Output

4
0
23
117