Vecinul grila[-1][j] nu dă eroare: indicii negativi trec de verificarea marginii
În Python, grila[-1] e ultimul rând, nu o eroare. Dacă verifici doar i < len(grila), vecinul de deasupra primului rând „există” și BFS/DFS-ul trece pe partea cealaltă a hărții. Verifică ambele margini: 0 <= i < randuri and 0 <= j < coloane.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
La parcurgerea unei grile (insule, lacuri, labirinturi, flood fill), fiecare celulă are patru vecini: (i-1, j), (i+1, j), (i, j-1), (i, j+1). Pe margini, unii nu există. În multe limbaje, indicele -1 ar da eroare și ai observa imediat. În Python, indicii negativi numără de la coadă: grila[-1] e ultimul rând, iar grila[0][-1] ultima coloană.
Dacă verificarea e doar i < len(grila), vecinul de deasupra primului rând trece de verificare și citește ultimul rând. Rezultatul: zone unite prin marginile opuse ale hărții, suprafețe prea mari, drumuri care „teleportează”. Nicio eroare, doar rezultate greșite.
Reparația e condiția completă: 0 <= ni < randuri and 0 <= nj < coloane, verificată înainte de a citi grila[ni][nj].
De ce apare: cauzele frecvente
1Doar marginea de jos și cea din dreapta
if ni < len(grila) and nj < len(grila[0]) and grila[ni][nj] == 1:
stiva.append((ni, nj))if 0 <= ni < len(grila) and 0 <= nj < len(grila[0]) and grila[ni][nj] == 1:
stiva.append((ni, nj))0 <= ni exclude indicii negativi, pe care Python i-ar accepta fără eroare.
2Verificarea marginii prin try/except IndexError
try:
if grila[ni][nj] == 1:
stiva.append((ni, nj))
except IndexError:
passif 0 <= ni < len(grila) and 0 <= nj < len(grila[0]):
if grila[ni][nj] == 1:
stiva.append((ni, nj))IndexError prinde doar ieșirile în dreapta și jos. Indicii -1 nu dau eroare, deci try nu ajută.
Repară eroarea, direct în pagină
Funcția suprafata(grila, i, j) calculează câte celule de uscat (1) sunt legate de celula de start, mergând în sus, jos, stânga și dreapta. Testul cu assert pică: suprafața iese prea mare. Repar-o ca testele să treacă și să afișeze 3 și 1.
def suprafata(grila, i, j):
vazute = {(i, j)}
stiva = [(i, j)]
while stiva:
r, c = stiva.pop()
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if nr < len(grila) and nc < len(grila[0]) and grila[nr][nc] == 1 and (nr, nc) not in vazute:
vazute.add((nr, nc))
stiva.append((nr, nc))
return len(vazute)
grila = [[1, 1, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 0],
[1, 0, 0, 1]]
for start, corect in [((0, 0), 3), ((3, 3), 1)]:
rez = suprafata(grila, *start)
assert rez == corect, f'suprafata gresita: {rez}'
print(rez)3 1
Indiciu
Vecinul e valid doar dacă și rândul, și coloana sunt cel puțin 0.
Reparația
def suprafata(grila, i, j):
vazute = {(i, j)}
stiva = [(i, j)]
while stiva:
r, c = stiva.pop()
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < len(grila) and 0 <= nc < len(grila[0]) and grila[nr][nc] == 1 and (nr, nc) not in vazute:
vazute.add((nr, nc))
stiva.append((nr, nc))
return len(vazute)
grila = [[1, 1, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 0],
[1, 0, 0, 1]]
for start, corect in [((0, 0), 3), ((3, 3), 1)]:
rez = suprafata(grila, *start)
assert rez == corect, f'suprafata gresita: {rez}'
print(rez)De ce merge
Din (0, 0), vecinul de sus e (-1, 0). Condiția veche verifica doar nr < len(grila), deci îl accepta, iar grila[-1][0] e celula din colțul de jos-stânga, care e uscat. Așa, două zone separate erau numărate împreună. Cu 0 <= nr și 0 <= nc, vecinii din afara hărții sunt ignorați, iar suprafața de la (0, 0) e corect 3: (0, 0), (0, 1) și (1, 1).
Cum o eviți pe viitor
Scrie o funcție mică in_grila(i, j) care verifică 0 <= i < R and 0 <= j < C și folosește-o peste tot. Ține direcțiile într-o listă (DIRECTII = [(-1, 0), (1, 0), (0, -1), (0, 1)]) ca să nu repeți condițiile. Testează mereu pornind dintr-un colț al grilei, unde două direcții ies din hartă, și pune ceva pe marginea opusă.
Întrebări frecvente
De ce nu primesc IndexError la -1?
Pentru că lista[-1] e o operație validă în Python: ultimul element. Eroarea apare doar sub -len(lista).
Pot evita verificarea punând o bordură în jurul grilei?
Da, o margine de celule „apă” sau „zid” pe toate laturile elimină verificările, dar indicii se decalează cu 1. E o tehnică validă, doar fii consecvent.
Erori înrudite
IndexError: list index out of range la parcurgerea unei matrice Ai inversat numărul de rânduri cu numărul de coloane (sau i cu j) la o matrice care nu e pătrată. len(grila) e numărul de rânduri, len(grila[0]) e numărul de coloane, iar accesul se face mereu grila[rand][coloana]. BFS-ul nu se mai oprește pe un graf cu ciclu (lipsesc nodurile vizitate) BFS-ul pune în coadă vecinii fără să verifice dacă au mai fost descoperiți, iar pe un graf cu ciclu (sau neorientat) aceleași noduri intră în coadă la nesfârșit; editorul oprește programul după limita de timp. Marchează nodul ca vizitat când îl pui în coadă. [[0] * m] * n: modifici o celulă și se schimbă toată coloana [[0] * m] * n nu creează n rânduri, ci n referințe la același rând, așa că dp[0][1] = 5 apare în toate rândurile. Creează fiecare rând separat: [[0] * m for _ in range(n)]. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
