Parcurgeri speciale ale matricei

Pe lângă parcurgerea clasică (linie cu linie), există parcurgeri mai complexe care apar frecvent la concursuri: în spirală, în zigzag și pe diagonale paralele.

Parcurgerea în spirală

Parcurgem matricea de la exterior spre interior, ca o spirală care se strânge:

Matrice 4 x 4:

 1 →  2 →  3 →  4
                ↓
12 → 13 → 14    5
↑              ↓
11   16 ← 15    6
↑              ↓
10 ←  9 ←  8 ← 7

Ordinea: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

Ideea

Menținem 4 limite: sus, jos, stanga, dreapta. La fiecare pas parcurgem o latură și micșorăm limitele.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[101][101];
int n, m;

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            fin >> a[i][j];

    int sus = 1, jos = n, stanga = 1, dreapta = m;

    while (sus <= jos && stanga <= dreapta) {
        // Linia de sus: stânga → dreapta
        for (int j = stanga; j <= dreapta; j++)
            fout << a[sus][j] << " ";
        sus++;

        // Coloana din dreapta: sus → jos
        for (int i = sus; i <= jos; i++)
            fout << a[i][dreapta] << " ";
        dreapta--;

        // Linia de jos: dreapta → stânga
        if (sus <= jos) {
            for (int j = dreapta; j >= stanga; j--)
                fout << a[jos][j] << " ";
            jos--;
        }

        // Coloana din stânga: jos → sus
        if (stanga <= dreapta) {
            for (int i = jos; i >= sus; i--)
                fout << a[i][stanga] << " ";
            stanga++;
        }
    }

    return 0;
}

date.in:

date.out:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Pas cu pas

Iterație	sus	jos	stânga	dreapta	Ce parcurgem
1	1	4	1	4	Linia 1: 1,2,3,4 / Coloana 4: 5,6,7 / Linia 4: 8,9,10 / Coloana 1: 11,12
2	2	3	2	3	Linia 2: 13,14 / Coloana 3: 15 / Linia 3: 16

Generarea spiralei

Problema inversă: construim o matrice n x n cu valorile 1, 2, …, n² în spirală.

int val = 1;
int sus = 1, jos = n, stanga = 1, dreapta = n;

while (sus <= jos && stanga <= dreapta) {
    for (int j = stanga; j <= dreapta; j++)
        a[sus][j] = val++;
    sus++;

    for (int i = sus; i <= jos; i++)
        a[i][dreapta] = val++;
    dreapta--;

    if (sus <= jos) {
        for (int j = dreapta; j >= stanga; j--)
            a[jos][j] = val++;
        jos--;
    }

    if (stanga <= dreapta) {
        for (int i = jos; i >= sus; i--)
            a[i][stanga] = val++;
        stanga++;
    }
}

Rezultat pentru n=4:

 1  2  3  4
12 13 14  5
11 16 15  6
10  9  8  7

Parcurgerea în zigzag

Parcurgem liniile alternativ: prima de la stânga la dreapta, a doua de la dreapta la stânga, și tot așa.

 → → → →
 ← ← ← ←
 → → → →
 ← ← ← ←

for (int i = 1; i <= n; i++) {
    if (i % 2 == 1) {
        // Linie impară: stânga → dreapta
        for (int j = 1; j <= m; j++)
            fout << a[i][j] << " ";
    } else {
        // Linie pară: dreapta → stânga
        for (int j = m; j >= 1; j--)
            fout << a[i][j] << " ";
    }
}

Exemplu:

Matrice:
1 2 3
4 5 6
7 8 9

Zigzag: 1 2 3 6 5 4 7 8 9

Parcurgerea pe diagonale paralele cu diagonala secundară

Parcurgem diagonalele de la colțul stânga-sus spre dreapta-jos. Fiecare diagonală are aceeași sumă i + j.

Matrice 3 x 3, diagonalele (i+j):

i+j=2: a[1][1]
i+j=3: a[1][2], a[2][1]
i+j=4: a[1][3], a[2][2], a[3][1]
i+j=5: a[2][3], a[3][2]
i+j=6: a[3][3]

for (int s = 2; s <= n + m; s++) {
    for (int i = 1; i <= n; i++) {
        int j = s - i;
        if (j >= 1 && j <= m)
            fout << a[i][j] << " ";
    }
    fout << endl;
}

Exemplu:

Matrice:
1 2 3
4 5 6
7 8 9

Diagonale: 
1
2 4
3 5 7
6 8
9

Parcurgerea pe diagonale paralele cu diagonala principală

Fiecare diagonală are aceeași diferență i - j.

Matrice 3 x 3, diagonalele (i-j):

i-j=-2: a[1][3]
i-j=-1: a[1][2], a[2][3]
i-j= 0: a[1][1], a[2][2], a[3][3]  ← diag principală
i-j= 1: a[2][1], a[3][2]
i-j= 2: a[3][1]

for (int d = -(m - 1); d <= n - 1; d++) {
    for (int i = 1; i <= n; i++) {
        int j = i - d;
        if (j >= 1 && j <= m)
            fout << a[i][j] << " ";
    }
    fout << endl;
}

Parcurgerea pe coloane zigzag

Prima coloană de sus în jos, a doua de jos în sus, etc.

for (int j = 1; j <= m; j++) {
    if (j % 2 == 1) {
        for (int i = 1; i <= n; i++)
            fout << a[i][j] << " ";
    } else {
        for (int i = n; i >= 1; i--)
            fout << a[i][j] << " ";
    }
}

Tabel rezumativ

Parcurgere	Idee	Complexitate
Pe linii	`for i, for j`	O(n*m)
Pe coloane	`for j, for i`	O(n*m)
Spirală	4 limite: sus, jos, stânga, dreapta	O(n*m)
Zigzag	Linii alternativ stânga-dreapta	O(n*m)
Diagonale (i+j)	Parcurgem după suma i+j	O(n*m)
Diagonale (i-j)	Parcurgem după diferența i-j	O(n*m)

Greșeli frecvente

1. Spirala pe matrice ne-pătratică

Algoritmul de spirală funcționează și pe matrici dreptunghiulare, dar trebuie verificări suplimentare (if (sus <= jos) și if (stanga <= dreapta)) pentru a nu parcurge aceeași linie/coloană de două ori.

2. Indicii ies din matrice la diagonale

Când parcurgem diagonalele, j = s - i poate fi negativ sau mai mare decât m. Verificăm mereu j >= 1 && j <= m.

3. Zigzag - uitarea inversării

Dacă uiți condiția i % 2, parcurgi toate liniile în aceeași direcție.

Ce să reții

Spirala: 4 limite care se strâng, parcurgem o latură la fiecare pas.
Zigzag: alternăm direcția la fiecare linie (sau coloană).
Diagonale paralele (i+j): elementele cu aceeași sumă i + j sunt pe aceeași diagonală.
Diagonale paralele (i-j): elementele cu aceeași diferență i - j sunt pe aceeași diagonală.
Toate parcurgerile au complexitate O(n*m) - fiecare element e vizitat o singură dată.