Parcurgeri pe diagonale — i+j și i−j sunt constante

De ce contează?

La jocul X și 0 verifici dacă cineva a câștigat pe diagonală: colț cu colț, oblic. Nu te uiți pe rânduri sau coloane, ci pe linia înclinată. Ca să prinzi acea linie într-o matrice, ai nevoie de o regulă simplă între linie și coloană.

Cele două diagonale principale

Într-o matrice pătratică (n × n) există două diagonale speciale:

Diagonala principală (stânga-sus → dreapta-jos): elementele cu i == j.
Diagonala secundară (dreapta-sus → stânga-jos): elementele cu i + j == n - 1.

Observația-cheie

Truc de aur: pe o diagonală „" (ca principala), i − j e constant. Pe o diagonală „/" (ca secundara), i + j e constant. Aceste două sume/diferențe identifică orice diagonală.

Exemplu pe numere

Matricea a (4×4):

L0	1	2	3	4
	0	1	2	3

a[0][0]=1 (principală), a[0][3]=4 (secundară)

L1	5	6	7	8
	0	1	2	3

L2	9	1	2	3
	0	1	2	3

L3	4	5	6	7
	0	1	2	3

a[3][3]=7 (principală), a[3][0]=4 (secundară)

Diagonala principală (i == j): 1, 6, 2, 7.
Diagonala secundară (i + j == 3): 4, 7, 1, 4.

Implementare C++

#include <iostream>
using namespace std;

int a[100][100];

int main() {
    int n;
    cin >> n; // matrice patratica
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    int sumaP = 0, sumaS = 0;
    for (int i = 0; i < n; i++) {
        sumaP += a[i][i];         // principala: i == j
        sumaS += a[i][n - 1 - i]; // secundara: j = n-1-i
    }
    cout << "Diagonala principala: " << sumaP << "\n";
    cout << "Diagonala secundara: " << sumaS << "\n";
    return 0;
}

O singură buclă ajunge: pentru fiecare i, elementul principal e a[i][i], iar cel secundar a[i][n-1-i].

Diagonale paralele

Toate diagonalele „" se grupează după i − j. Pentru o matrice n × n, i − j ia valori de la -(n-1) la n-1. Poți aduna pe fiecare diagonală folosind d = i - j ca etichetă (cu un decalaj ca să fie pozitiv):

// suma fiecarei diagonale paralele cu cea principala
int sumaDiag[200] = {0}; // indexat dupa (i - j + n)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        sumaDiag[i - j + n] += a[i][j]; // decalaj +n ca sa fie index pozitiv

Analog, pentru diagonalele „/" folosești i + j (valori 0..2n-2).

Complexitate

Operație	Timp	Spațiu
O diagonală	O(n)	O(1)
Toate diagonalele	O(n²)	O(n) etichete

Vizualizare

Urmărește cum elementele de pe aceeași diagonală împart aceeași valoare i − j (sau i + j):

Greșeli frecvente

Greșeli frecvente de concurs:

Formula secundarei greșită. Elementul secundar pe linia i e a[i][n-1-i], nu a[i][n-i] (care iese din matrice cu un pas).
Index negativ la diagonale paralele. i - j poate fi negativ. Adaugă un decalaj (+ n) ca să-l folosești ca index de vector.
Aplici pe matrice nepătratică. „Diagonala principală” clasică e definită pe matrice pătratică. Pe n ≠ m, regula i == j merge doar până la min(n, m).
Numeri de două ori centrul. La n impar, elementul din mijloc e pe ambele diagonale. Dacă aduni „principală + secundară”, el se numără de două ori — scade-l o dată dacă problema cere altfel.

Recapitulare

Diagonala principală: i == j; secundară: i + j == n - 1.
Diagonale paralele „" au i − j constant; cele „/" au i + j constant.
Centrul (la n impar) e pe ambele diagonale — atenție la dubla numărare.