Parcurgerea unei Matrice în Spirală în C++ 29

---

1. Obiectivele lecției:

• Să înțeleagă algoritmul pentru parcurgerea unei matrice în spirală.
• Să implementeze un algoritm în C++ care parcurge și afișează o matrice în ordine spirală.
• Să aplice acest concept pentru probleme practice care implică manipularea matricelor.

---

2. Conținutul lecției:

---

Ce înseamnă parcurgerea în spirală?

• Definiție: Parcurgerea în spirală a unei matrice implică citirea elementelor în ordinea lor, pornind de la marginea superioară, deplasându-se spre dreapta, în jos, spre stânga, și apoi în sus, continuând spre interior până când toate elementele sunt parcurse.
• Exemplu:
  • Matricea inițială: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]​​
  • Parcurgere spirală: 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10

---

Algoritmul de parcurgere în spirală

1. Definire limite:
   • sus (rândul superior), inițial 0.
   • jos (rândul inferior), inițial n−1.
   • stânga (coloana din stânga), inițial 0.
   • dreapta (coloana din dreapta), inițial m−1.
2. Parcurgere pe direcții:
   • Parcurge de la stânga la dreapta pe linia sus.
   • Parcurge de sus în jos pe coloana dreapta.
   • Parcurge de la dreapta la stânga pe linia jos (dacă este validă).
   • Parcurge de jos în sus pe coloana stânga (dacă este validă).
3. Actualizare limite:
   • După fiecare parcurgere, actualizează limitele: crește sus, scade jos, crește stânga, scade dreapta.
4. Oprește parcurgerea: Dacă toate limitele se intersectează.

---

Pseudocod:

sus = 0, jos = n – 1

stânga = 0, dreapta = m – 1

Cât timp sus <= jos și stânga <= dreapta:

    – Parcurge linia `sus` de la `stânga` la `dreapta`, apoi `sus++`

    – Parcurge coloana `dreapta` de la `sus` la `jos`, apoi `dreapta–`

    – Dacă `sus <= jos`, parcurge linia `jos` de la `dreapta` la `stânga`, apoi `jos–`

    – Dacă `stânga <= dreapta`, parcurge coloana `stânga` de la `jos` la `sus`, apoi `stânga++`

---

3. Cod în C++

---

Implementare completă:

#include <iostream>

using namespace std;

void parcurgereSpirala(int mat[][4], int n, int m) {

    int sus = 0, jos = n – 1;

    int stanga = 0, dreapta = m – 1;

    cout << „Elementele matricei in spirala: „;

    while (sus <= jos && stanga <= dreapta) {

        // Parcurge linia de sus (stânga -> dreapta)

        for (int i = stanga; i <= dreapta; i++) {

            cout << mat[sus][i] << ” „;

        }

        sus++;

        // Parcurge coloana din dreapta (sus -> jos)

        for (int i = sus; i <= jos; i++) {

            cout << mat[i][dreapta] << ” „;

        }

        dreapta–;

        // Parcurge linia de jos (dreapta -> stânga)

        if (sus <= jos) {

            for (int i = dreapta; i >= stanga; i–) {

                cout << mat[jos][i] << ” „;

            }

            jos–;

        }

        // Parcurge coloana din stânga (jos -> sus)

        if (stanga <= dreapta) {

            for (int i = jos; i >= sus; i–) {

                cout << mat[i][stanga] << ” „;

            }

            stanga++;

        }

    }

    cout << endl;

}

int main() {

    int mat[4][4] = {

        {1, 2, 3, 4},

        {5, 6, 7, 8},

        {9, 10, 11, 12},

        {13, 14, 15, 16}

    };

    cout << „Matricea initiala:” << endl;

    for (int i = 0; i < 4; i++) {

        for (int j = 0; j < 4; j++) {

            cout << mat[i][j] << ” „;

        }

        cout << endl;

    }

    parcurgereSpirala(mat, 4, 4);

    return 0;

}

---

4. Complexitatea algoritmului

1. Complexitate temporală: O(n⋅m), unde n este numărul de rânduri, iar mmm este numărul de coloane, deoarece fiecare element este vizitat o singură dată.
2. Complexitate spațială: O(1), deoarece nu necesită spațiu suplimentar.

---

5. Activități practice pentru elevi

1. Modificați algoritmul pentru a parcurge matricea în spirală în sens invers (din interior spre exterior).
2. Scrieți un program care determină suma elementelor parcurse în ordine spirală.
3. Realizați o funcție care stochează elementele parcurse în spirală într-un vector și îl afișează.

---

6. Scheme logice

1. Parcurgerea în spirală:
   • Start -> Inițializează limitele (sus, jos, stânga, dreapta) -> Parcurge secțiunile matricei -> Actualizează limitele -> Stop.

---

7. Concluzie:

• Parcurgerea în spirală este o tehnică fundamentală pentru procesarea matricelor, fiind aplicabilă în algoritmi complexi, inclusiv procesarea imaginilor și grafica pe calculator.
• Implementarea eficientă a acestui algoritm ajută elevii să înțeleagă manipularea limitelor și structura matricială.