4081 - alpinistii

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

Exemplu1

Intrare:

alpinisti.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

Iesire:

alpinisti.out

13

Exemplu2

Intrare:

alpinisti.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 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

Iesire:

alpinisti.out

9

Rezolvare

<syntaxhighlight lang="python" line="1">

def validare(n, m, matrice):

   if n < 1 or n > 200:
       return False
   if m < 1 or m > 200:
       return False
   for i in range(n):
       if len(matrice[i]) != m:
           return False
       for j in range(m):
           if matrice[i][j] != '0' and matrice[i][j] != '1':
               return False
   return True

def rezolvare1(n, m, matrice):

   max_spatii = 0
   for i in range(n):
       for j in range(m):
           if matrice[i][j] == '0':
               count = 0
               queue = [(i, j)]
               while queue:
                   x, y = queue.pop(0)
                   if matrice[x][y] == '0':
                       count += 1
                       matrice[x][y] = '1'
                       if x > 0 and matrice[x-1][y] == '0':
                           queue.append((x-1, y))
                       if x < n-1 and matrice[x+1][y] == '0':
                           queue.append((x+1, y))
                       if y > 0 and matrice[x][y-1] == '0':
                           queue.append((x, y-1))
                       if y < m-1 and matrice[x][y+1] == '0':
                           queue.append((x, y+1))
               max_spatii = max(max_spatii, count)
   return max_spatii

def rezolvare2(n, m, matrice):

   # initializam matricea dp cu 0-uri
   dp = [[0] * m for _ in range(n)]

   # calculam lățimea și înălțimea maximă a unui dreptunghi de spații sigure care include fiecare element
   for i in range(n-1, -1, -1):
       for j in range(m-1, -1, -1):
           if matrice[i][j] == '0':
               w = dp[i][j+1] + 1 if j < m-1 else 1
               h = dp[i+1][j] + 1 if i < n-1 else 1
               dp[i][j] = min(w, h)

   # calculam aria maximă a unui dreptunghi format doar din spații sigure din matrice
   max_area = 0
   for i in range(n):
       for j in range(m):
           if matrice[i][j] == '0':
               area = dp[i][j] * dp[i][j]
               max_area = max(max_area, area)

   return max_area

if __name__ == '__main__':

   with open('alpinisti.in', 'r') as f:
       cerinta, n, m = map(int, f.readline().strip().split())
       matrice = [list(f.readline().strip().split()) for _ in range(n)]

   if cerinta == 1:
       if not validare(n, m, matrice):
           with open('alpinisti.out', 'w') as f:
               f.write('Date de intrare invalide')
       else:
           max_spatii = rezolvare1(n, m, matrice)
           with open('alpinisti.out', 'w') as f:
               f.write(str(max_spatii))

   elif cerinta == 2:
       max_spatii = rezolvare2(n, m,matrice)
       with open('alpinisti.out', 'w') as f:
           f.write(str(max_spatii))

</syntaxhighlight>

Explicații

Acest cod este o soluție pentru problema "Alpiniști" și se împarte în trei funcții:

1. 1 Funcția validare(n, m, matrice) are rolul de a verifica dacă datele de intrare sunt valide. În cazul de față, se verifică dacă n și m se află în intervalul [1, 200] și dacă matricea matrice are dimensiunea corespunzătoare și conține doar caracterele '0' și '1'. Această verificare este importantă pentru a ne asigura că programul primește date valide și poate produce un rezultat corect.

1. 2 Funcția rezolvare1(n, m, matrice) calculează numărul maxim de spații sigure care pot fi găsite în matricea dată. Se parcurge fiecare element al matricei și se verifică dacă acesta este un spațiu sigur ('0'). Dacă este, se inițializează un contor la 0 și se adaugă poziția elementului într-o coadă. Apoi, se parcurge coada și se verifică dacă poziția curentă este un spațiu sigur. Dacă da, se incrementează contorul, se marchează spațiul ca fiind vizitat și se adaugă în coadă toți vecinii săi care sunt spații sigure și nu au fost deja vizitați. Acest proces continuă până când coada este goală și se înregistrează numărul maxim de spații sigure găsite până în acel moment. Această metodă se bazează pe algoritmul de căutare în lățime (BFS) și ne permite să găsim numărul maxim de spații sigure în matricea dată.

1. 3 Funcția rezolvare2(n, m, matrice) calculează aria maximă a unui dreptunghi format doar din spații sigure din matricea dată. În această funcție se folosește o metodă de programare dinamică. Se construiește o matrice dp cu aceleași dimensiuni ca și matricea matrice, inițializată cu zero. Pentru fiecare element din matricea matrice care este un spațiu sigur ('0'), se calculează lățimea maximă și înălțimea maximă a unui dreptunghi de spații sigure care include acel element, iar apoi se calculează aria maximă a dreptunghiului care conține acel element. Această metodă se bazează pe observația că orice dreptunghi format doar din spații sigure trebuie să includă un element din matricea matrice și că putem folosi matricea dp pentru a evita să re-calculăm dreptunghiuri în mod repetat.

1. 4 În if __name__ == '__main__': se deschide fișierul de intrare 'alpinisti.in' și se citesc datele de intrare. Apoi, în funcția main(), se verifică dacă datele de intrare sunt valide folosind funcția validare(). Dacă acestea sunt valide, se calculează numărul maxim de spații sigure și aria maximă a unui dreptunghi format doar din spații sigure, folosind funcțiile rezolvare1() și rezolvare2(). Aceste valori sunt apoi scrise în fișierul de ieșire 'alpinisti.out'.