RaulOtet: Pagină nouă: 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 su...

2024-07-26T08:12:49Z

Pagină nouă: 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 su...

New page

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 <code>N</code> linii și <code>M</code> coloane având doar valori de <code>0</code> și <code>1</code>, unde <code>0</code> înseamnă suprafață fără copac iar <code>1</code> î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 <code>mostenire.in</code> conține pe prima linie două numere naturale <code>N</code> și <code>M</code> separate prin exact un spațiu reprezentând dimensiunea pădurii. Pe fiecare dintre următoarele <code>N</code> linii se găsesc exact <code>M</code> caractere fără spațiu între ele, având doar valori de <code>0</code> și de <code>1</code>.

= Date de ieșire =
Fișierul de ieșire <code>mostenire.out</code> va conține un număr reprezentând răspunsul cerut de Fibocel.

= Restricții și precizări =

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

= Exemplu: =
<code>mostenire.in</code>
5 4
1111
1010
1111
1010
1110
<code>mostenire.out</code>
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")

# 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>

3299 - Mostenire 2 - Revision history