Diagonale — AlgoClar

De ce contează?

Pe o tablă de șah, nebunul se mișcă pe diagonale. Observi că, mergând pe o diagonală, diferența dintre rând și coloană rămâne mereu aceeași. Această regularitate simplă — o sumă sau o diferență constantă — e cheia parcurgerii diagonalelor.

Cele două diagonale principale

Într-o matrice pătratică n×n:

Diagonala principală: elementele cu i == j → (0,0), (1,1), ..., (n−1,n−1).
Diagonala secundară: elementele cu i + j == n − 1 → (0,n−1), (1,n−2), ..., (n−1,0).

Pe matricea de mai jos, diagonala principală e 1, 5, 9; secundara e 3, 5, 7.

1 2 3
4 5 6
7 8 9

diag	1	5	9
i=j	0	1	2

Diagonala principală extrasă ca vector: a[0][0]=1, a[1][1]=5, a[2][2]=9. Un singur indice o parcurge.

Parcurgerea diagonalelor principale

#include <iostream>
using namespace std;

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

    long long sumaPrinc = 0, sumaSec = 0;
    for (int i = 0; i < n; i++) {
        sumaPrinc += a[i][i];           // i == j
        sumaSec   += a[i][n - 1 - i];   // i + j == n-1
    }
    cout << sumaPrinc << " " << sumaSec << "\n";
    return 0;
}

Cu un singur indice i parcurgi ambele diagonale: a[i][i] și a[i][n-1-i].

Observația-cheie

Nu ai nevoie de două bucle imbricate pentru o diagonală — una singură ajunge, fiindcă al doilea indice se deduce din primul (j = i sau j = n-1-i). O diagonală e, practic, un vector.

Toate diagonalele, nu doar cele principale

Elementele de pe aceeași diagonală au un invariant:

paralele cu principala → i − j constant.
paralele cu secundara → i + j constant.

Pentru o matrice m×n, suma i + j ia valori de la 0 la m+n−2 — fiecare valoare e o diagonală secundară. Le poți grupa după i + j:

// elementele cu i+j == s sunt pe aceeasi diagonala secundara
for (int s = 0; s <= m + n - 2; s++) {
    for (int i = 0; i < m; i++) {
        int j = s - i;
        if (j >= 0 && j < n) {
            // a[i][j] e pe diagonala s
        }
    }
}

Complexitate

Operație	Timp	Spațiu
o diagonală principală	O(n)	O(1)
toate diagonalele	O(m·n)	O(1)

Greșeli frecvente

Capcane reale la diagonale:

Confuzi principala cu secundara: principala i == j, secundara i + j == n − 1. Verifică pe un exemplu mic (3×3).
Indice greșit la secundară: a[i][n - i] iese din matrice la i = 0. Corect e a[i][n - 1 - i].
Folosești două bucle pentru o diagonală: inutil — al doilea indice se deduce din primul.
Margini la diagonalele paralele: când grupezi după i + j, verifică j să fie în [0, n−1], altfel ieși din matrice.

Vizualizare

Urmărește cum diagonalele se conturează: elementele de pe aceeași diagonală au i − j (sau i + j) constant.

Indiciu

Observă că o diagonală se parcurge cu un singur indice care avansează — al doilea se deduce. Diagonalele paralele „alunecă" una după alta peste matrice.

De reținut

Diagonala principală: i == j; secundara: i + j == n − 1 (acces a[i][n-1-i]).
O diagonală e un vector — un singur indice o parcurge.
Diagonalele paralele au i − j (cu principala) sau i + j (cu secundara) constant.