Fişierul intrare/ieşire:tetris2.in, tetris2.outSursăLot 2008 - Piatra Neamt, Baraj1
AutorDan-Ionut FecheteAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Tetris2

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, Bi,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, Pi,j fiind numarul de cuburi asezate pe patratul de pe linia i si coloana j al bazei piesei (1≤i,j≤N).

figura 1 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
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.

Date de intrare

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.

Date de iesire

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.

Restrictii

  • 2 ≤ M ≤ 504
  • 1 ≤ N ≤ 100
  • N ≤ M-1
  • 1 ≤ Mi,j ≤ 10000 (1 ≤ i,j ≤ M)
  • 1 ≤ Pi,j ≤ 10000 (1 ≤ i,j ≤ N)

Exemplu

tetris2.intetris2.out
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

Explicatie

Piesa poate fi pozitionata perfect doar in pozitia (1,3).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content