Clasa a X-a · Tablouri bidimensionale (matrice)Read in English

Parcurgerea în spirală în C++

În engleză: Spiral traversal

O(n²)C++1767 de linii2 exemple

Ideea

Ținem patru margini: sus, jos, stanga, dreapta. La fiecare tură parcurgem linia de sus (spre dreapta), coloana din dreapta (în jos), linia de jos (spre stânga) și coloana din stânga (în sus), apoi strângem marginile cu câte o poziție. Verificările sus <= jos și stanga <= dreapta din mijlocul turei evită afișarea de două ori a unei linii sau coloane rămase singure (matrice dreptunghiulare).

Descrierea în engleză

We keep four borders: top, bottom, left, right. On every lap we walk the top row (to the right), the right column (down), the bottom row (to the left) and the left column (up), then move each border in by one. The checks top <= bottom and left <= right in the middle of the lap avoid printing a lone remaining row or column twice (rectangular matrices).

Complexitate
O(n * m), fiecare element este afișat o singură dată
Clasa
Clasa a X-a (Grade 10)

Exemple

Exemplul 1

Intrare

3 4
1 2 3 4
5 6 7 8
9 10 11 12

Ieșire așteptată

1 2 3 4 8 12 11 10 9 5 6 7
Exemplul 2

Intrare

3 3
1 2 3
4 5 6
7 8 9

Ieșire așteptată

1 2 3 6 9 8 7 4 5

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

parcurgere-in-spirala.cpp
/*
 * Titlu: Parcurgerea în spirală
 * Clasa: 10
 * Capitol: Tablouri bidimensionale (matrice)
 * Descriere: Ținem patru margini: sus, jos, stanga, dreapta. La fiecare tură
 *            parcurgem linia de sus (spre dreapta), coloana din dreapta (în jos),
 *            linia de jos (spre stânga) și coloana din stânga (în sus), apoi
 *            strângem marginile cu câte o poziție. Verificările sus <= jos și
 *            stanga <= dreapta din mijlocul turei evită afișarea de două ori a
 *            unei linii sau coloane rămase singure (matrice dreptunghiulare).
 * Complexitate: O(n * m), fiecare element este afișat o singură dată
 *
 * Exemplu
 * Intrare:
 * 3 4
 * 1 2 3 4
 * 5 6 7 8
 * 9 10 11 12
 * Ieșire: 1 2 3 4 8 12 11 10 9 5 6 7
 *
 * Exemplu
 * Intrare:
 * 3 3
 * 1 2 3
 * 4 5 6
 * 7 8 9
 * Ieșire: 1 2 3 6 9 8 7 4 5
 */
#include <iostream>
using namespace std;

int a[101][101];

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];

    int sus = 1, jos = n, stanga = 1, dreapta = m;
    while (sus <= jos && stanga <= dreapta)
    {
        for (int j = stanga; j <= dreapta; j++)
            cout << a[sus][j] << ' ';
        sus++;
        for (int i = sus; i <= jos; i++)
            cout << a[i][dreapta] << ' ';
        dreapta--;
        if (sus <= jos)
        {
            for (int j = dreapta; j >= stanga; j--)
                cout << a[jos][j] << ' ';
            jos--;
        }
        if (stanga <= dreapta)
        {
            for (int i = jos; i >= sus; i--)
                cout << a[i][stanga] << ' ';
            stanga++;
        }
    }
    cout << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.