...
Eroare Algoritmi și structuri de date · Grafuri: BFS și DFS

Vecinul grila[-1][j] nu dă eroare: indicii negativi trec de verificarea marginii

Pe scurt

Î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

Greșit
PYTHON
if ni < len(grila) and nj < len(grila[0]) and grila[ni][nj] == 1:
    stiva.append((ni, nj))
Corect
PYTHON
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

Greșit
PYTHON
try:
    if grila[ni][nj] == 1:
        stiva.append((ni, nj))
except IndexError:
    pass
Corect
PYTHON
if 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ă tu

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.

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
3
1
Indiciu

Vecinul e valid doar dacă și rândul, și coloana sunt cel puțin 0.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.