Parcurgeri în matrice

De ce contează?

O tablă de șah are rânduri și coloane; ca să spui unde e un pion, dai două coordonate: rândul și coloana. O matrice e exact asta — un tabel de valori unde fiecare element are o adresă din două numere: linia și coloana.

Ce este o matrice

O matrice e un tablou bidimensional: valori așezate în linii și coloane. a[i][j] e elementul de pe linia i, coloana j. Indicii pornesc de la 0: o matrice cu m linii și n coloane are liniile 0..m−1 și coloanele 0..n−1.

int a[100][100];        // matrice de pana la 100x100

Parcurgerea linie cu linie

Cea mai comună parcurgere folosește două bucle imbricate: cea exterioară fixează linia, cea interioară trece prin toate coloanele ei.

#include <iostream>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    int a[100][100];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];         // citire linie cu linie

    long long suma = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            suma += a[i][j];        // prelucrare: suma tuturor elementelor

    cout << suma << "\n";
    return 0;
}

Pentru matricea de mai jos, parcurgerea row-major vizitează în ordine: 1, 2, 3, 4, 5, 6.

1 2 3
4 5 6

Observația-cheie

Ordinea buclelor dă ordinea vizitării. for i { for j } parcurge linie cu linie (stânga→dreapta, sus→jos). Inversând buclele (for j { for i }) parcurgi coloană cu coloană. Rezultatul unei sume e același, dar ordinea contează când afișezi sau cauți „primul" element cu o proprietate.

Parcurgeri pe o linie sau o coloană

O linie fixă i: treci prin coloane → a[i][0], a[i][1], ..., a[i][n-1].
O coloană fixă j: treci prin linii → a[0][j], a[1][j], ..., a[m-1][j].

a[1]	4	5	6
j	0	1	2

Linia 1 a matricei, privită ca un vector: a[1][0]=4, a[1][1]=5, a[1][2]=6. O linie e un vector obișnuit.

Complexitate

Operație	Timp	Spațiu
parcurgerea întregii matrice	O(m·n)	O(1) suplimentar
o singură linie sau coloană	O(n) sau O(m)	O(1)

Parcurgerea completă vizitează fiecare element o dată → O(m·n), proporțional cu numărul de celule.

Greșeli frecvente

Capcane reale la parcurgerea matricelor:

Inversezi i și j: scrii a[j][i] în loc de a[i][j] → accesezi alt element sau ieși din matrice dacă m ≠ n. Linia mereu prima.
Off-by-one pe 2D: condiții i <= m sau j <= n accesează linii/coloane inexistente. Folosește i < m, j < n.
Confuzi dimensiunile: la o matrice m×n, prima dimensiune e numărul de linii. Declară a[m][n] cu m și n în ordinea corectă.
Bucle în ordine greșită pentru afișare: suma iese la fel, dar afișarea coloană-cu-coloană arată matricea „transpusă".

Vizualizare

Urmărește cum cele două bucle imbricate vizitează celulele, linie cu linie, în ordine:

Indiciu

Observă că indicele j (coloana) se schimbă rapid, iar i (linia) abia după ce o linie întreagă a fost parcursă. Asta e ordinea row-major.

De reținut

a[i][j] = linia i, coloana j; indici 0..m−1 și 0..n−1.
Parcurgere row-major: for i { for j }; ordinea buclelor dă ordinea vizitării.
Parcurgerea completă e O(m·n); o linie/coloană e un vector obișnuit.