Crosswords#9688
To attract more tourists to Paris, Anne plans to organize a large sound-and-light show at night on the facades of the Louvre Palace. The facades contain windows arranged in several levels, aligned both horizontally and vertically.
Anne has the idea of displaying giant letters in the windows—one letter per window—so that complete words are formed both horizontally and vertically.
On a given facade, the windows form a rectangular grid with rows and columns.
Anne has prepared:
a list of words of length (to be displayed vertically),
a list of words of length (to be displayed horizontally).
Your task is to determine how many different ways there are to fill the grid such that:
each row forms a valid horizontal word,
each column forms a valid vertical word.
Count the number of distinct letter grids of size n \times m such that:
each of the rows, read from left to right, is a word from the horizontal list;
each of the columns, read from top to bottom, is a word from the vertical list.
Two grids are considered different if they differ in at least one cell.
The input consists of the following:
The first line contains two integers n~(2 \le n \le 4) and ;
The second line contains two integers m~(2 \le m \le 4) and b~(1 \le a \times b \le 1008016);
The next lines each contain a word of length (vertical words);
The next lines each contain a word of length (horizontal words)
Constraints:
All words consist only of lowercase English letters (a - z);
Each list contains no duplicate words;
Words may be reused multiple times in different rows or columns
Special Case. If n = m, then:
a word from the vertical list cannot be used horizontally unless it also appears in the horizontal list;
a word from the horizontal list cannot be used vertically unless it also appears in the vertical list
Print the total number of distinct valid word grids.
Sample 1:
Sample 2:
Esempio 1
Esempio 2