Andrei este un maestru al jocului de tetris, il poate juca zile intregi cu ochii inchisi si cu mainile legate la spate. De aceea el a hotarat sa treaca la un alt nivel si sa joace varianta 3D a jocului. Piesele vor cadea pe o suprafata plana orizontala de forma patrata, cu latura de $M cm$, denumita baza. Pe baza este trasat un caroiaj ce delimiteaza $MxM$ patratele de latura $1 cm$, fiecare patratel fiind identificat prin coordonatele sale (linia si coloana pe care se afla). Dupa caderea unor piese pe baza, se obtine o anumita configuratie de joc, ce va fi reprezentata ca o matrice $B$ cu $M$ linii si $M$ coloane, $B{~i,j~}$ fiind inaltimea atinsa de cel mai inalt cub plasat pe patratelul de pe linia $i$ si coloana $j$ al matricei $(1≤i,j≤M)$ - vezi figura 1. O piesa a jocului se obtine prin lipirea unor cuburi de latura $1 cm$ pe o suprafata plana (baza piesei) - vezi figura 2. O piesa va fi reprezentata de asemenea ca o matrice $P$ cu $N$ linii si $N$ coloane, $P{~i,j~}$ fiind numarul de cuburi asezate pe patratul de pe linia $i$ si coloana $j$ al bazei piesei $(1≤i,j≤N)$.
|a|b|
|!problema/tetris2?fig1.bmp! figura 1|!problema/tetris2?fig2.bmp! figura 2|
|Configuratia bazei din figura 1 va fi descrisa de urmatoarea matrice:
$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$|d|
$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$|Piesa din figura 2 va fi descrisa de urmatoarea matrice:
$1 2 1$
$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") ==
