Xoay ma trận 90 độ không dùng bộ nhớ thêm (theo chiều kim đồng hồ) bằng C++

Xoay ma trận vuông N×N 90 độ theo chiều kim đồng hồ (clockwise) tại chỗ (in-place), không dùng mảng phụ.

Ví dụ

Input:
5 1 4
9 16 12
2 8 9

Output (xoay 90° CW):
2 9 5
8 16 1
9 12 4

Phương pháp 1: Xoay theo vòng (Layer by Layer) - Naive

Tương tự xoay ngược, nhưng đổi chỗ 4 phần tử theo chiều kim đồng hồ: top→right, right→bottom, bottom→left, left→top.

Mã nguồn Naive

#include <bits/stdc++.h>
using namespace std;
#define N 3

void rotateCW(int mat[N][N]) {
    for (int layer = 0; layer < N/2; layer++) {
        int first = layer, last = N - 1 - layer;
        for (int i = first; i < last; i++) {
            int offset = i - first;
            int top = mat[first][i];
            // left -> top
            mat[first][i] = mat[last - offset][first];
            // bottom -> left
            mat[last - offset][first] = mat[last][last - offset];
            // right -> bottom
            mat[last][last - offset] = mat[i][last];
            // top -> right
            mat[i][last] = top;
        }
    }
}

int main() {
    int mat[N][N] = {{5,1,4}, {9,16,12}, {2,8,9}};
    rotateCW(mat);
    cout << "Ma trận xoay 90° CW:\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) cout << mat[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

Phương pháp 2: Chuyển vị + Đảo cột (Efficient)

Xoay 90° CW = Chuyển vị (Transpose) + Đảo thứ tự cột (Reverse columns).

• Chuyển vị: mat[i][j] ↔ mat[j][i] cho i < j.
• Đảo cột: đổi cột j với cột N-1-j.

Mã nguồn Efficient

#include <bits/stdc++.h>
using namespace std;
#define N 3

void rotateCW(int mat[N][N]) {
    // Transpose
    for (int i = 0; i < N; i++)
        for (int j = i+1; j < N; j++)
            swap(mat[i][j], mat[j][i]);
    // Reverse columns
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N/2; j++)
            swap(mat[i][j], mat[i][N-1-j]);
}

int main() {
    int mat[N][N] = {{5,1,4}, {9,16,12}, {2,8,9}};
    rotateCW(mat);
    cout << "Ma trận xoay 90° CW:\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) cout << mat[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

Kết quả (cả 2 phương pháp)

2 9 5
8 16 1
9 12 4

Kết luận

Bài viết so sánh 2 cách xoay ma trận 90° CW in-place: xoay theo vòng và chuyển vị + đảo cột. Cách 2 (Transpose + Reverse columns) đơn giản, ít lỗi, khuyến nghị sử dụng. Mã C++ đầy đủ cho cả hai phương pháp.