Numărul de insule dintr-o hartă
Scrie numar_insule(harta) și aria_maxima(harta) pentru o hartă dată ca listă de texte ('1' = uscat, '0' = apă), cu 4 vecini (sus, jos, stânga, dreapta). Nu modifica harta primită: lucrează pe o copie de tip listă de liste.
- Copiază harta:
grila = [list(rand) for rand in harta]. - Pentru fiecare celulă
'1': crești contorul și pornești un DFS care transformă insula în'0'. - Pentru arie, DFS-ul întoarce
1 + suma ariilor vecinilor, iar tu păstrezi maximul. - Trebuie să apară: 1, 3, 0, 1, 9, 4, 0 și la final
11000(harta originală neschimbată).
grila[r][c]: r < 0 or r >= randuri or c < 0 or c >= coloane.def numar_insule(harta):
grila = [list(rand) for rand in harta]
randuri = len(grila)
coloane = len(grila[0]) if grila else 0
def scufunda(r, c):
if r < 0 or r >= randuri or c < 0 or c >= coloane or grila[r][c] != '1':
return
grila[r][c] = '0'
scufunda(r - 1, c)
scufunda(r + 1, c)
scufunda(r, c - 1)
scufunda(r, c + 1)
insule = 0
for r in range(randuri):
for c in range(coloane):
if grila[r][c] == '1':
insule += 1
scufunda(r, c)
return insule
def aria_maxima(harta):
grila = [list(rand) for rand in harta]
randuri = len(grila)
coloane = len(grila[0]) if grila else 0
def arie(r, c):
if r < 0 or r >= randuri or c < 0 or c >= coloane or grila[r][c] != '1':
return 0
grila[r][c] = '0'
return 1 + arie(r - 1, c) + arie(r + 1, c) + arie(r, c - 1) + arie(r, c + 1)
maxim = 0
for r in range(randuri):
for c in range(coloane):
if grila[r][c] == '1':
maxim = max(maxim, arie(r, c))
return maxim
harta1 = ['11110',
'11010',
'11000',
'00000']
harta2 = ['11000',
'11000',
'00100',
'00011']
harta3 = ['000',
'000']
print(numar_insule(harta1))
print(numar_insule(harta2))
print(numar_insule(harta3))
print(numar_insule(['1']))
print(aria_maxima(harta1))
print(aria_maxima(harta2))
print(aria_maxima(harta3))
print(harta2[0])


