Numărul de insule dintr-o hartă
O imagine din satelit a unei zone de coastă devine o grilă: 1 = uscat, 0 = apă. Câte insule sunt? Problema este printre cele mai populare la interviuri și nu are niciun graf explicit: grila este graful. Fiecare celulă e un nod, iar vecinii ei sunt celulele de sus, jos, stânga și dreapta.
Grila ca graf implicit
Nu construiești liste de adiacență: vecinii celulei (r, c) se calculează pe loc cu patru deplasări. Singura grijă este să nu ieși din hartă.
harta = ['110',
'010',
'001']
randuri, coloane = len(harta), len(harta[0])
directii = [(-1, 0), (1, 0), (0, -1), (0, 1)] # sus, jos, stânga, dreapta
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ă).
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan