🔲 Matrici

Capitolul 5 — Parcurgere, diagonale, transpusă, rotire, matrice pătratice speciale și probleme BAC

MatriciDiagonaleTranspusăSpiralăTablouri 2D
📖 12 min
0
📋

Declararea și citirea matricelor

O matrice (tablou bidimensional) stochează date în rânduri și coloane, accesate prin doi indici: a[linie][coloana].

int a[101][101];  // matrice de maxim 100×100
int n, m;       // n linii, m coloane

// Citire
cin >> n >> m;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        cin >> a[i][j];

// Afișare
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++)
        cout << a[i][j] << " ";
    cout << endl;
}
Memorie: O(n×m)

Stocată pe linii în RAM (row-major order)

Acces element: O(1)

a[i][j] — acces direct prin indici

🔁

Parcurgere — sumă, minim, maxim

Suma elementelor pe linii și coloane

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

// Suma pe fiecare linie
for (int i = 1; i <= n; i++) {
    int sumaLinie = 0;
    for (int j = 1; j <= m; j++)
        sumaLinie += a[i][j];
    cout << "Suma linia " << i << ": " << sumaLinie << endl;
}

Minimul și poziția sa

int minim = a[1][1], linMin = 1, colMin = 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        if (a[i][j] < minim) {
            minim = a[i][j];
            linMin = i; colMin = j;
        }
Complexitate parcurgere completă: O(n×m) — sau O(n²) pentru matrice pătratică n×n.
📐

Diagonalele matricei pătratice

Pentru matrice pătratică n×n (indexată de la 1):
• Diagonala principală: elemente unde i == j
• Diagonala secundară: elemente unde i + j == n + 1
Atenție — două convenții de indexare!
IndexareDiagonala principalăDiagonala secundarăExemplu n=5
de la 1 (BAC, standard) i == j i + j == n + 1 (1,5),(2,4),(3,3),(4,2),(5,1) — suma i+j = 6 = n+1
de la 0 (C++ array) i == j i + j == n - 1 (0,4),(1,3),(2,2),(3,1),(4,0) — suma i+j = 4 = n-1

La BAC se folosește exclusiv indexarea de la 1. Condiția pentru diagonala secundară este i + j == n + 1, iar accesul în cod este a[i][n-i+1].

// Suma diagonalei principale
int sumaDiagP = 0;
for (int i = 1; i <= n; i++)
    sumaDiagP += a[i][i];

// Suma diagonalei secundare
int sumaDiagS = 0;
for (int i = 1; i <= n; i++)
    sumaDiagS += a[i][n-i+1];

Triunghiul superior și inferior

// Suma elementelor DEASUPRA diagonalei principale (triunghi superior)
int sumaSup = 0;
for (int i = 1; i <= n; i++)
    for (int j = i+1; j <= n; j++)  // j > i
        sumaSup += a[i][j];

// Suma elementelor SUB diagonala principală (triunghi inferior)
int sumaInf = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j < i; j++)  // j < i
        sumaInf += a[i][j];
Proprietate: Suma totală = sumaDiagP + sumaSup + sumaInf (dacă diagonalele nu se suprapun)
🎮 Demo interactiv — Diagonale și zone

Apasă pe un buton pentru a evidenția zona corespunzătoare. Suma elementelor evidențiate apare în dreapta.

Sumă: —
diag. principală diag. secundară triunghi sup. triunghi inf. bordură
↔️

Transpusa matricei

Transpusa matricei A este matricea B unde B[i][j] = A[j][i] — liniile devin coloane și viceversa.

// Transpusa în matrice separată (funcționează și pentru dreptunghice)
int t[101][101];  // t are m linii și n coloane
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        t[j][i] = a[i][j];
// Transpusa IN-PLACE pentru matrice PĂTRATICĂ (n×n)
for (int i = 1; i <= n; i++)
    for (int j = i+1; j <= n; j++)
        swap(a[i][j], a[j][i]);  // interschimbăm deasupra diagonalei
Exemplu:
A = [[1,2,3],[4,5,6]] → Aᵀ = [[1,4],[2,5],[3,6]]
🎮 Demo interactiv — Transpusa in-place

Pentru o matrice 4×4, executăm swap(a[i][j], a[j][i]) pentru fiecare j > i. Vor fi exact n(n−1)/2 = 6 interschimbări.

Normal
Interschimbări: 0
a[i][j] a[j][i] final
🔄

Rotirea matricei cu 90°

Rotirea unei matrice n×n cu 90° în sens orar: b[j][n-i+1] = a[i][j]

// Rotire 90° sens orar (Clockwise)
int b[101][101];
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        b[j][n-i+1] = a[i][j];

// Rotire 90° sens antiorar (Counter-Clockwise)
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        b[n-j+1][i] = a[i][j];
Rotire 180° = rotire 90° aplicată de două ori, sau direct: b[n-i+1][n-j+1] = a[i][j]
🎮 Demo interactiv — Rotire 90°

Sursa în stânga, destinația în dreapta. Fiecare celulă din A își găsește locul în B.

Normal
A (sursa)
B (rotită)
⭐

Matrice pătratice speciale

Matrice simetrică față de diagonala principală

bool esteSimetrica = true;
for (int i = 1; i <= n && esteSimetrica; i++)
    for (int j = 1; j < i; j++)
        if (a[i][j] != a[j][i]) esteSimetrica = false;

Matrice cu borduri (cadru)

// Suma elementelor de pe bordul matricei
int sumaBord = 0;
for (int j = 1; j <= m; j++) sumaBord += a[1][j] + a[n][j];  // liniile 1 și n
for (int i = 2; i < n; i++)  sumaBord += a[i][1] + a[i][m];   // coloanele 1 și m

Umplere cu 0 a bordurilor

for (int j = 1; j <= m; j++) a[1][j] = a[n][j] = 0;
for (int i = 1; i <= n; i++) a[i][1] = a[i][m] = 0;

Matrice identitate

// Creare matrice identitate n×n
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        a[i][j] = (i == j) ? 1 : 0;
🌀

Parcurgere în spirală

Problemă clasică: Parcurgeți și afișați elementele matricei în ordine spirală (exterior → interior, sens orar). 
void spirala(int a[][101], int n, int m) {
    int top = 1, bot = n, left = 1, right = m;

    while (top <= bot && left <= right) {
        for (int j = left; j <= right; j++)  cout << a[top][j] << " ";  top++;
        for (int i = top; i <= bot; i++)    cout << a[i][right] << " ";  right--;
        if (top <= bot) {
            for (int j = right; j >= left; j--) cout << a[bot][j] << " ";  bot--;
        }
        if (left <= right) {
            for (int i = bot; i >= top; i--)   cout << a[i][left] << " ";   left++;
        }
    }
}
Exemplu n=3: [[1,2,3],[4,5,6],[7,8,9]] → 1 2 3 6 9 8 7 4 5
🎮 Demo interactiv — Parcurgere în spirală 5×5

Urmărește celula curentă (galben) și ordinea de vizitare (mov). Output-ul se construiește pas cu pas.

Normal
Ieșire:
🔢

Demo Interactiv — Zone Matrice 5×5

🗺️ Cum recunosc zonele în matrice?

O matrice pătratică n×n are mai multe zone speciale. Elementul de pe linia i și coloana j aparține:

  • Diagonalei principale dacă i == j
  • Diagonalei secundare dacă i + j == n + 1
  • Triunghiului superior dacă j > i
  • Triunghiului inferior dacă j < i
  • Bordurii dacă i==1 || i==n || j==1 || j==n

Apasă butoanele de mai jos pentru a vedea evidențiată fiecare zonă:

Diag. principală
Diag. secundară
Ambele diagonale
Triunghi superior
Triunghi inferior
Bordură
🧩

Probleme rezolvate — matrici

5 probleme clasice cu enunț, exemplu și soluție comentată.

1 Maxim pe fiecare linie Ușor
Citește o matrice n × m (1 ≤ n, m ≤ 50). Afișează maximul de pe fiecare linie, în ordinea liniilor.
Intrare:
3 4
1 5 2 7
9 3 1 4
6 6 8 2
Ieșire:
7 9 8
💡 Vezi soluția 
#include <iostream>
using namespace std;
int a[55][55];
int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) {
        int mx = a[i][1];
        for (int j = 2; j <= m; j++)
            if (a[i][j] > mx) mx = a[i][j];
        cout << mx << " ";
    }
    return 0;
}

Idee: pentru fiecare linie, inițializăm mx cu primul element și actualizăm pe rest. Complexitate O(n·m).

2 Suma triunghiului superior strict Ușor
Pentru o matrice pătratică n × n, afișează suma elementelor strict deasupra diagonalei principale (j > i).
Intrare:
3
1 2 3
4 5 6
7 8 9
Ieșire:
11
💡 Vezi soluția 
int sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)  // j > i ⇒ strict deasupra
        sum += a[i][j];
cout << sum;

Pe exemplu: 2 + 3 + 6 = 11. Atenție: dacă cerea „inclusiv diagonala", condiția ar fi j >= i.

3 Matrice simetrică? Mediu
Verifică dacă o matrice pătratică n × n este simetrică față de diagonala principală (a[i][j] == a[j][i] pentru orice i, j). Afișează DA sau NU.
Intrare:
3
1 2 3
2 5 4
3 4 9
Ieșire:
DA
💡 Vezi soluția 
bool sim = true;
for (int i = 1; i <= n && sim; i++)
    for (int j = 1; j < i && sim; j++)   // doar sub diagonală
        if (a[i][j] != a[j][i]) sim = false;
cout << (sim ? "DA" : "NU");

Optimizare: verificăm doar jumătate (j < i), pentru că (i,j) și (j,i) sunt simetrice; cu break-ul prin sim ieșim imediat ce găsim o nepotrivire.

4 Coloana cu suma maximă Mediu
Citește o matrice n × m și afișează indicele coloanei cu suma maximă a elementelor. Dacă sunt mai multe, afișează prima.
Intrare:
3 3
1 2 3
4 5 6
7 8 9
Ieșire:
3
💡 Vezi soluția 
int idxMax = 1, sumMax = 0;
for (int i = 1; i <= n; i++) sumMax += a[i][1];
for (int j = 2; j <= m; j++) {
    int s = 0;
    for (int i = 1; i <= n; i++) s += a[i][j];
    if (s > sumMax) { sumMax = s; idxMax = j; }
}
cout << idxMax;

Pe exemplu: coloana 1: 12, coloana 2: 15, coloana 3: 18 → răspuns 3. Bucla externă pe j, internă pe i ⇒ parcurgem matricea pe coloane.

5 Rotire 90° in-place (4 swap-uri/strat) Dificil
Rotește o matrice pătratică n × n cu 90° în sens orar, folosind doar O(1) memorie suplimentară (in-place).
Intrare:
3
1 2 3
4 5 6
7 8 9
Ieșire:
7 4 1
8 5 2
9 6 3
💡 Vezi soluția 
// Truc: transpunere + inversare a fiecărei linii
// 1) Transpunere in-place
for (int i = 1; i <= n; i++)
    for (int j = i+1; j <= n; j++) swap(a[i][j], a[j][i]);
// 2) Inversăm fiecare linie
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n/2; j++) swap(a[i][j], a[i][n-j+1]);

De ce funcționează: transpunerea reflectă matricea pe diagonala principală; inversarea liniilor adaugă reflexia verticală. Compunerea celor două reflexii = rotație 90° CW. Complexitate O(n²), memorie O(1).

Pentru CCW: transpunere + inversare a fiecărei coloane.

💪 Vezi quiz-ul de la final și problemele BAC din secțiunea următoare pentru și mai multă practică.
📝

Probleme tip BAC — matrici

Problemă 1 (BAC 2023): Dată o matrice pătratică n×n, verificați dacă este matrice magică (suma pe orice linie, coloană sau diagonală este aceeași).
Soluție: 
bool esteMagica(int a[][101], int n) {
    int suma = 0;
    for (int i=1; i<=n; i++) suma += a[1][i];  // suma primei linii
    for (int i=2; i<=n; i++) {
        int s=0; for (int j=1;j<=n;j++) s+=a[i][j];
        if(s!=suma) return false;
    }
    for (int j=1; j<=n; j++) {
        int s=0; for (int i=1;i<=n;i++) s+=a[i][j];
        if(s!=suma) return false;
    }
    int d1=0, d2=0;
    for (int i=1;i<=n;i++) { d1+=a[i][i]; d2+=a[i][n-i+1]; }
    return (d1==suma && d2==suma);
}
Problemă 2: Dată o matrice n×m, rotiți toate elementele de pe borduri cu o poziție în sens orar (fără elementele interioare).
Indiciu: Salvați elementul din colțul stânga-sus, deplasați liniile și coloanele de margine pe rând, restaurați elementul salvat.
💪

Exerciții interactive — testează cunoștințele