Alpiniștii

Time limit: 0.05s Memory limit: 4MB Input: alpinistii.in Output: alpinistii.out

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 Nord, Sud, Est și Vest, 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 00, iar valorile de 11 reprezintă spațiile blocate.

Ei vă cer ajutorul pentru a reuși să-i salveze pe alpiniști.

Cerință

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 00 din matricea dată.

Date de intrare

Fișierul de intrare alpinistii.in conține pe prima linie trei numere naturale: cc, nn și mm, separate prin câte un spațiu, cc reprezentând numărul cerinței ce urmează a fi rezolvată (11 sau 22), nn reprezentând numărul de linii ale matricei, iar mm numărul de coloane. Fiecare dintre următoarele nn linii conține câte mm cifre de 00 și 11, 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

  • 1n,m2001 \leq n, m \leq 200
  • În matrice sunt doar valori de 00 și 11.
  • Pentru rezolvarea corectă a cerinței 11 se acordă 4040 puncte, iar pentru cerința 22 se acordă 6060 puncte.

Exemplul 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ă (1313 spații sigure), celelalte zone-adăpost au: 55 spații sigure (verde), 44 spații sigure (maro) și 11 spațiu sigur (albastru).

Exemplul 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 99 (zona înconjurată cu galben). Se observă că matricea conține și alte două zone dreptunghiulare formate din câte 88 spații sigure (zonele inconjurate cu maro și verde).

Log in or sign up to be able to send submissions!