Pracsiu Dan (dnprx) Elevii din clasa mea vor să își decoreze clasa și au nevoie de mai multe tablouri. Niciun copil din clasă nu are talent la desen. Copiii au procurat un afiș de la un eveniment internațional și s-au gândit să decupeze din afiș mai multe tablouri. Tablourile trebuie să aibă formă dreptunghiulară și să conțină un singur obiect, care nu poate fi tăiat; obiectul poate fi înconjurat sau nu de fundal. Spunem că un obiect poate fi încadrat într-un tablou dacă se poate decupa un tablou care să îl conțină. Unii copii doresc tablouri mai mari, alții doresc tablouri mai mici. Copiii au la dispoziție un singur afiș motiv pentru care nu pot face încercări, deci tablourile trebuie să fie decupate din prima încercare. De aceea ei au apelat la colegii lor olimpici la informatică. Astfel afișul a fost reprezentat ca o matrice cu N linii și M coloane, elementele care fac parte dintr-un obiect sunt memorate cu valori nenule, iar elementele care fac parte din fundal sunt reprezentate cu 0. Două elemente din matrice fac parte din același obiect dacă au aceeași valoare nenulă și sunt adiacente pe linie sau pe coloană. Definim suprafața unui obiect ca fiind numărul de elemente ale matricei care fac parte din obiect.
Cerința
Cunoscând N, M numărul de linii respectiv numărul de coloane din matrice și elementele matricei care reprezintă afișul, scrieţi un program care să rezolve următoarele cerinţe:
1. Determină aria minimă a unui tablou care conține obiectul de suprafață maximă care poate fi încadrat într-un tablou;
2. Determină numărul maxim de tablouri care pot fi decupate știind că elevii caută începând de sus în jos și de la stânga la dreapta obiectele care pot fi încadrate într-un tablou și decupează tabloul.
Date de intrare
Fişierul de intrare tablou.in conţine pe prima linie un număr natural C reprezentând cerinţa care trebuie să fie rezolvată (1 sau 2). Pe a doua linie a fișierului de intrare se află două numere naturale N M, separate printr-un spațiu, care reprezintă numărul de linii și de coloane ale matricei care reprezintă afișul. Următoarele N linii conțin câte M numere naturale care reprezintă elementele matricei care descrie afișul. Elementele unei linii sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire tablou.out va conține răspunsul la cerinţa C specificată în fişierul de intrare. Dacă C = 1 fişierul va conţine un număr natural, reprezentând aria minimă a tabloului ce conține obiectul de suprafață maximă care poate fi încadrat într-un tablou. Dacă C = 2 fişierul va conţine un număr natural, reprezentând numărul maxim de tablouri care pot fi decupate știind că elevii caută începând de sus în jos și de la stânga la dreapta obiectele care pot fi încadrate într-un tablou.
Restricții și precizări
1 ≤ N, M ≤ 100- Elementele matricei sunt cifre zecimale
- Pentru teste valorând 45 de puncte
C = 1. Pentru teste valorând alte 45 de puncteC = 2. - 10 puncte se acordă pentru testele din enunț.
Exemplul 1:
tablou.in
1 5 6 0 0 1 1 0 0 1 1 1 0 2 2 0 0 0 2 2 0 0 0 2 2 0 3 0 0 0 0 3 3
tablou.out
8
Exemplul 2:
tablou.in
2 5 6 0 0 1 1 0 0 1 1 1 0 2 2 0 0 0 2 2 0 0 0 2 2 0 3 0 0 0 0 3 3
tablou.out
2