3299 - Mostenire 2

Fibocel tocmai a moștenit o pădure gigantică de formă dreptunghiulară pe care vrea să o transforme într-un parc de distracții pentru copii. Cum își dă seama că este foarte mult de lucru și nu știe de unde să înceapă, s-a decis ca mai întâi să numere câte pădurici se află în pădurea moștenită. O pădurice este o suprafață dreptunghiulară înconjurată în totalitate de copaci, cu cel puțin o poieniță oriunde în interior. O poieniță este o suprafață fără copaci. Cum Fibocel și-a dat seama că și acest lucru este dificil de realizat, s-a decis să vă ceară vouă ajutorul!

Cerința

Dându-se pădurea moștenită de Fibocel sub forma unui dreptunghi cu N linii și M coloane având doar valori de 0 și 1, unde 0 înseamnă suprafață fără copac iar 1 înseamnă suprafață cu copac, spuneți câte pădurici se regăsesc în interiorul pădurii moștenite.

Date de intrare

Fișierul de intrare mostenire.in conține pe prima linie două numere naturale N și M separate prin exact un spațiu reprezentând dimensiunea pădurii. Pe fiecare dintre următoarele N linii se găsesc exact M caractere fără spațiu între ele, având doar valori de 0 și de 1.

Date de ieșire

Fișierul de ieșire mostenire.out va conține un număr reprezentând răspunsul cerut de Fibocel.

Restricții și precizări

• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 1000
• Păduricile se pot intersecta între ele.
• Pentru 15% dintre teste N, M ≤ 30.
• Pentru alte 35% dintre teste, M ≤ 100.

Exemplu:

mostenire.in

5 4
1111
1010
1111
1010
1110

mostenire.out

3

<syntaxhighlight lang="python" line="1"> def citire_date(nume_fisier):

   with open(nume_fisier, 'r') as f:
       N, M = map(int, f.readline().split())
       matrice = [list(map(int, f.readline().split())) for _ in range(N)]
   return N, M, matrice

def verifica_dreptunghi(matrice, x1, y1, x2, y2):

   # Verificam marginile dreptunghiului
   for i in range(x1, x2 + 1):
       if matrice[i][y1] != 1 or matrice[i][y2] != 1:
           return False
   for j in range(y1, y2 + 1):
       if matrice[x1][j] != 1 or matrice[x2][j] != 1:
           return False
   
   # Verificam daca exista cel putin un 0 in interior
   for i in range(x1 + 1, x2):
       for j in range(y1 + 1, y2):
           if matrice[i][j] == 0:
               return True

   return False

def numara_padurici(N, M, matrice):

   numar_padurici = 0
   
   for x1 in range(N):
       for y1 in range(M):
           for x2 in range(x1 + 1, N):
               for y2 in range(y1 + 1, M):
                   if verifica_dreptunghi(matrice, x1, y1, x2, y2):
                       numar_padurici += 1
   
   return numar_padurici

def scrie_rezultate(nume_fisier, numar_padurici):

   with open(nume_fisier, 'w') as f:
       f.write(f"{numar_padurici}\n")

1. Main function

def main():

   N, M, matrice = citire_date('date.in')
   numar_padurici = numara_padurici(N, M, matrice)
   scrie_rezultate('date.out', numar_padurici)

if __name__ == '__main__':

   main()

</syntaxhighlight>