Rezolvare PBinfo #4081

Enunț

Un grup de alpiniști, aflați pe marginea unei stânci de pe un versant, sunt prinși în mijlocul unei furtuni. Pentru a se adăposti, ei trebuie să găsească o zonă-adăpost din versant formată din spații sigure învecinate în direcțiile N, E, S și V, suficient de mare, astfel încât în ea să se poată adăposti întregul grup. Alpiniștii au, pe căștile lor, montate camere care trimit o filmare video, în direct, la o echipă de programatori salvamontiști. Informaticienii reușesc să analizeze spațiile sigure ale versantului și să reprezinte versantul cu ajutorul unei matrice binare. Fiecare spațiu sigur este codificat cu 0, iar valorile de 1 reprezintă spațiile blocate.
Ei vă cer ajutorul pentru a reuși să-i salveze pe alpiniști.

Cerința

Cunoscând matricea binară ce codifică versantul, determinați:
1) Numărul maxim de spații sigure ce pot forma o zonă-adăpost de pe versant
2) Numărul maxim de spații sigure dintr-o zonă-adăpost dreptunghiulară corespunzătoare unui dreptunghi format doar din valori de 0 din matricea dată.

Date de intrare

Fișierul de intrare alpinistii.in conține pe prima linie trei numere naturale: c, n și m, separate prin câte un spațiu, c reprezentând numărul cerinței ce urmează a fi rezolvată (1 sau 2), n reprezentând numărul de linii ale matricei, iar m numărul de coloane. Fiecare dintre următoarele n linii conține câte m cifre de 0 și 1, separate prin câte un spațiu, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire alpinistii.out va conține pe prima linie un număr natural reprezentând răspunsul la cerința care se rezolvă.

Restricții și precizări

• 1 ≤ n ≤ 200
• 1 ≤ m ≤ 200
• în matrice sunt doar valori de 0 și 1
• Pentru rezolvarea corectă a cerinței 1 se acordă 40 puncte, iar pentru cerința 2 se acordă 60 puncte.

Exemplu 1:

alpinistii.in

1
7 8
1 1 1 1 1 1 1 1 
1 0 0 1 1 1 1 0 
1 1 0 1 0 0 0 1 
1 1 0 1 0 0 1 1 
0 1 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
1 0 0 1 1 1 1 1

alpinistii.out

13

Explicație

Zona-adăpost înconjurată cu galben este cea mai mare posibilă (13 spații sigure), celelalte zone-adăpost au: 5 spații sigure (verde), 4 spații sigure (maro) și 1 spațiu sigur (albastru).

Exemplu 2:

alpinistii.in

2
7 8
1 1 1 1 1 1 1 1 
1 0 0 1 1 1 1 0 
1 1 0 1 0 0 1 1 
1 1 0 1 0 0 0 1 
0 1 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
1 0 0 1 1 1 1 1

alpinistii.out

9

Explicație

Numărul maxim de spații sigure ce formează o zonă-adăpost dreptunghiulară este 9 (zona înconjurată cu galben). Se observă că matricea conține și alte două zone dreptunghiulare formate din câte 8 spații sigure (zonele inconjurate cu maro și verde).