Parcurgerea în spirală a unei matrice în C++

Parcurgerea în spirală afișează conturul matricei, apoi conturul rămas în interior, până când toate celulele au fost vizitate. Pornim din colțul stânga sus și mergem spre dreapta, apoi în jos, spre stânga și în sus.

Exemplul care fixează direcția

Pentru o matrice de 3×4, cu liniile 1 2 3 4, 5 6 7 8, 9 10 11 12, rezultatul este 1 2 3 4 8 12 11 10 9 5 6 7. Primele zece valori formează conturul; 6 și 7 sunt linia interioară rămasă. Această descriere este și un mod de a desena traseul pe hârtie, fără ambiguități despre orientare.

Citim 1 ≤ n,m ≤ 100 și n·m numere întregi. Matricea clasică are capacitatea 100×100, iar domeniul folosit este 0..n-1 pe linii și 0..m-1 pe coloane.

Spirala pornește din colțul stânga sus, urmărește conturul și se termină cu valorile 6 și 7.Mărește schema ↗

Cele patru limite

sus, jos, st și dr delimitează dreptunghiul încă neafișat. După parcurgerea unei laturi, mutăm limita ei spre interior. Înainte de latura de jos și cea din stânga verificăm dacă mai există linia sau coloana necesară. Aceste verificări împiedică afișarea aceleiași celule de două ori.

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    int a[100][100];
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    int sus=0, jos=n-1, st=0, dr=m-1, scrise=0;
    auto scrie = [&](int x) { if(scrise++) cout << ' '; cout << x; };
    while(sus<=jos && st<=dr) {
        for(int j=st;j<=dr;++j) scrie(a[sus][j]);
        ++sus;
        for(int i=sus;i<=jos;++i) scrie(a[i][dr]);
        --dr;
        if(sus<=jos) {
            for(int j=dr;j>=st;--j) scrie(a[jos][j]);
            --jos;
        }
        if(st<=dr) {
            for(int i=jos;i>=sus;--i) scrie(a[i][st]);
            ++st;
        }
    }
    cout << '\n';
}

Varianta echivalentă cu std::vector

Indicii și datele de intrare rămân aceleași. Containerul este construit cu numărul de elemente folosite; accesul prin [] cere în continuare indici valizi.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    int sus=0, jos=n-1, st=0, dr=m-1, scrise=0;
    auto scrie = [&](int x) { if(scrise++) cout << ' '; cout << x; };
    while(sus<=jos && st<=dr) {
        for(int j=st;j<=dr;++j) scrie(a[sus][j]);
        ++sus;
        for(int i=sus;i<=jos;++i) scrie(a[i][dr]);
        --dr;
        if(sus<=jos) {
            for(int j=dr;j>=st;--j) scrie(a[jos][j]);
            --jos;
        }
        if(st<=dr) {
            for(int i=jos;i>=sus;--i) scrie(a[i][st]);
            ++st;
        }
    }
    cout << '\n';
}

Funcția locală scrie are doar rol de formatare: pune spațiu înaintea fiecărei valori, cu excepția primei. Capturarea [&] îi permite să actualizeze contorul scrise. Logica traseului este în cele patru bucle și nu depinde de acest mod de afișare.

Cazurile înguste

La o singură linie, prima buclă afișează tot. Limita sus trece peste jos, iar latura de jos nu se mai parcurge. La o singură coloană, afișăm celula de sus și restul coloanei în jos; verificarea st<=dr blochează revenirea pe aceeași coloană.

Pentru o matrice pătratică de dimensiune impară rămâne o celulă centrală. Ea este afișată ca o linie de lungime 1. Nu necesită o ramură specială. Numără valorile rezultate: trebuie să fie exact n·m, inclusiv când valorile din matrice sunt egale.

Fiecare celulă este vizitată o singură dată, deci timpul este O(n·m). Cele patru limite și contorul consumă O(1) memorie auxiliară, pe lângă matrice. Nu modificăm valorile pentru a marca vizitarea.

Exersează

Verifică manual o matrice 1×4, una 4×1 și una 2×2 înainte de un exemplu mare. Pentru 1 2 / 3 4, ordinea este 1 2 4 3. Pentru 1×1, singura valoare apare o dată.

Ca extensie, încearcă pornirea din colțul dreapta sus, în sens invers. Desenează mai întâi direcțiile și stabilește ce limită se modifică după fiecare latură.

Recapitulează indicii unei matrice, conturul și diagonalele și limitele buclelor.

Întrebări frecvente

Cum se parcurge o matrice în spirală?

Se vizitează conturul în ordinea sus, dreapta, jos, stânga, apoi se micșorează dreptunghiul rămas. Se repetă până când limitele se întâlnesc sau se depășesc.

De ce sunt necesare verificări în interiorul parcurgerii în spirală?

După eliminarea unei linii sau coloane poate să nu mai rămână nimic pe direcția următoare. Reverificarea limitelor împiedică afișarea repetată a celulelor unei linii sau coloane centrale.

Care este complexitatea parcurgerii în spirală?

Pentru n linii și m coloane, timpul este O(n·m), deoarece fiecare celulă este vizitată o singură dată. Cele patru limite ale dreptunghiului folosesc O(1) memorie auxiliară, fără a include matricea.