.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » tetris2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
tetris2


Timp maxim de execuţie / test:
0.4s
Memorie totala disponibilă / stivă:
16MB / 1MB

Andrei este un maestru al jocului de tetris, îl poate juca zile întregi cu ochii închişi şi cu mâinile legate la spate. De aceea el a hotărât să treaca la un alt nivel şi să joace varianta 3D a jocului.
Piesele vor cădea pe o suprafaţă plană orizontală de formă pătrată, cu latura de M cm, denumită baza. Pe bază este trasat un caroiaj ce delimitează MxM pătrăţele de latură 1 cm, fiecare pătrăţel fiind identificat prin coordonatele sale (linia şi coloana pe care se află).
După căderea unor piese pe bază, se obţine o anumită configuraţie de joc, ce va fi reprezentată ca o matrice B cu M linii şi M coloane, Bij fiind înălţimea atinsă de cel mai înalt cub plasat pe pătrăţelul de pe linia i şi coloana j al matricei (1≤i,j≤M) - vezi figura 1.
O piesă a jocului se obţine prin lipirea unor cuburi de latură 1 cm pe o suprafaţă plană (baza piesei) - vezi figura 2. O piesă va fi reprezentată de asemenea ca o matrice P cu N linii şi N coloane, Pij fiind numărul de cuburi aşezate pe pătratul de pe linia i şi coloana j al bazei piesei (1≤i,j≤N).



Configuraţia bazei din figura de mai sus va fi descrisă de următoarea 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




Piesa din figura precedenta va fi descrisă de următoarea matrice:
1 2 1
2 3 2
2 2 2

Fiecare pătrăţel al bazei piesei sau al bazei are cel puţin un cub aşezat pe el.
Piesele vor cădea cu baza piesei în sus şi nu pot fi rotite. O piesă se poziţionează pe bază astfel: se aliniază pătratul (1,1) al bazei piesei cu un pătrăţel (L,C) al matricei (fără ca piesa să depăşească limitele bazei), iar piesa cade vertical până când un cub al piesei atinge un cub al bazei.
Spunem că o piesă se poziţionează perfect într-o anumită poziţie (L,C) dacă pentru fiecare pătrăţel al bazei piesei cubul ″cel mai de jos″ atinge cubul situat la înălţime maximă de pe pătrăţelul bazei corespunzător.

Cerinţă

Date fiind configuraţia bazei şi o piesă, să se determine numărul de poziţii în care piesa poate fi poziţionată perfect.

Date de intrare

Fişierul de intrare tetris2.in conţine pe prima linie numărul natural M, reprezentând dimensiunea bazei. Următoarele M linii conţin câte M numere naturale separate prin spaţii, reprezentând matricea care codifică configuraţia bazei. Pe linia M+2 se află numărul natural N, reprezentând dimensiunea bazei piesei. Pe următoarele N linii se află câte N numere naturale separate prin spaţii, reprezentând matricea ce codifică piesa.

Date de ieşire

Fişierul de ieşire tetris2.out va conţine o singură linie pe care va fi scris numărul de poziţii în care piesa dată poate fi poziţionată perfect.

Restricţii

1 < M < 505
0 < N < 101
N < M
1 ≤ Mi,j ≤ 10000 (1≤i, j≤M)
1 ≤ Pi,j ≤ 10000 (1≤i, j≤N)

Exemple

tetris2.intetris2.outExplicaţii
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 Piesa poate fi poziţionată perfect doar în poziţia (1,3).

autor: Dan Ionut Fechete
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Despre KMP: KMP
Probleme recomandate
surse trimise | ajutor