$2 3 2$
$2 2 2$|
Fiecare patratel al bazei piesei sau al bazei are cel putin un cub asezat pe el. Piesele vor cadea cu baza piesei in sus si nu pot fi rotite. O piesa se pozitioneaza pe baza astfel: se aliniaza patratul $(1,1)$ al bazei piesei cu un patratel $(L,C)$ al matricei (fara ca piesa sa depaseasca limitele bazei), iar piesa cade vertical pana cand un cub al piesei atinge un cub al bazei. Spunem ca o piesa se pozitioneaza perfect intr-o anumita pozitie $(L,C)$ daca pentru fiecare patratel al bazei piesei cubul "cel mai de jos" atinge cubul situat la inaltime maxima de pe patratelul bazei corespunzator. Date fiind configuratia bazei si o piesa, sa se determine numarul de pozitii in care piesa poate fi pozitionata perfect.
h2. Date de intrare
Fisierul de intrare $tetris2.in$ ...
Fisierul de intrare $tetris2.in$ contine pe prima linie numarul natural $M$, reprezentand dimensiunea bazei. Urmatoarele $M$ linii contin cate $M$ numere naturale separate prin spatii, reprezentand matricea care codifica configuratia bazei. Pe linia $M+2$ se afla numarul natural $N$, reprezentand dimensiunea bazei piesei. Pe urmatoarele $N$ linii se afla cate $N$ numere naturale separate prin spatii, reprezentand matricea ce codifica piesa.
h2. Date de iesire
In fisierul de iesire $tetris2.out$ ...
Fisierul de iesire $tetris2.out$ va contine o singura linie pe care va fi scris numarul de pozitii in care piesa data poate fi pozitionata perfect.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 ≤ M ≤ 504$
* $1 ≤ N ≤ 100$
* $N ≤ M-1$
* $1 ≤ M{~i,j~} ≤ 10000 (1 ≤ i,j ≤ M)$
* $1 ≤ P{~i,j~} ≤ 10000 (1 ≤ i,j ≤ N)$
h2. Exemplu
table(example). |_. tetris2.in |_. tetris2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|6
3 2 3 2 3 2
2 1 2 1 2 4
2 1 2 2 2 1
2 1 1 2 1 1
2 1 1 2 1 1
3 1 2 1 2 1
3
1 2 1
2 3 2
2 2 2
|1
|
h3. Explicatie
...
Piesa poate fi pozitionata perfect doar in pozitia $(1,3)$.
== include(page="template/taskfooter" task_id="tetris2") ==
