Rotirea matricei cu 90 de grade în C++

Matricea cu liniile 1 2 3 și 4 5 6 devine, după rotirea cu 90 de grade în sensul acelor de ceasornic, matricea cu liniile 4 1, 5 2, 6 3. Două linii și trei coloane se transformă în trei linii și două coloane.

Coordonatele se schimbă împreună

O celulă (i,j) ajunge în (j,n-1-i), dacă matricea inițială are n linii. Coloana veche devine linia nouă. Linia veche devine o coloană numărată de la dreapta la stânga. Formula folosește n, nu m, pentru noua coloană.

Verifică formula pe colțuri: (0,0) ajunge în (0,n-1), deci stânga sus devine dreapta sus. Celula (n-1,0), stânga jos, ajunge în (0,0). Aceste două verificări fixează sensul rotației mai sigur decât memorarea formulei fără desen.

Citim 1≤n,m≤100 și n·m întregi. Afișăm m linii, fiecare cu n valori. Indicii interni pornesc de la zero. Tablourile clasice a și b au capacitatea 100×100, dar dreptunghiurile folosite au dimensiuni diferite.

Matricea 1,2,3 / 4,5,6 se rotește spre dreapta în 4,1 / 5,2 / 6,3. Elementul (i,j) ajunge la (j,n-1-i), unde n este numărul inițial de linii.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n,m; cin >> n >> m; int a[100][100],b[100][100];
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) b[j][n-1-i]=a[i][j];
    for(int i=0;i<m;++i) {
        for(int j=0;j<n;++j) cout << (j?" ":"") << b[i][j];
        cout << '\n';
    }
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n,m; cin >> n >> m; vector<vector<int>> a(n,vector<int>(m)),b(m,vector<int>(n));
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) cin >> a[i][j];
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) b[j][n-1-i]=a[i][j];
    for(int i=0;i<m;++i) {
        for(int j=0;j<n;++j) cout << (j?" ":"") << b[i][j];
        cout << '\n';
    }
}

De ce folosim o a doua matrice

Dacă scriem direct peste celulele din a, putem distruge valori care încă nu au fost mutate. Matricea separată b face corespondența simplă și funcționează și pentru un dreptunghi. Rotirea în același spațiu, fără o matrice suplimentară, este o altă implementare și cere un argument separat.

Fiecare celulă veche are o singură destinație, iar două celule diferite nu pot ajunge în aceeași destinație: din noua linie aflăm j, iar din noua coloană aflăm i. Astfel toate cele n·m valori sunt păstrate exact o dată.

Timpul este O(n·m), pentru citire, transfer și afișare. Memoria suplimentară pentru rezultat este O(n·m). Nu descriem soluția ca memorie constantă doar fiindcă dimensiunile tablourilor clasice sunt fixate în cod.

Exersează

Verifică o singură linie 1 2 3, care devine o coloană 1,2,3. O coloană cu 1,2,3 devine linia 3 2 1. Pentru o matrice 1×1, valoarea rămâne aceeași. Ca extensie, aplică patru rotații și verifică revenirea la matricea inițială, inclusiv dimensiunile.

Revezi citirea și transpunerea, parcurgerile matricelor și indicii tablourilor.

Întrebări frecvente

Care este formula rotirii unei matrice cu 90 de grade la dreapta?

Cu indici de la zero, celula (i,j) a unei matrice cu n linii ajunge în (j,n-1-i). Formula folosește numărul inițial de linii pentru noua coloană.

Ce dimensiuni are matricea după rotirea cu 90 de grade?

O matrice n×m devine m×n. De exemplu, o matrice cu două linii și trei coloane devine una cu trei linii și două coloane.

Este transpunerea același lucru cu rotirea la dreapta?

Nu. Transpunerea schimbă (i,j) în (j,i). Rotirea la dreapta include și inversarea unei direcții, astfel încât apare indicele n-1-i.