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

Xoay ma trận vuông N×N 90 độ ngược chiều kim đồng hồ (counter-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° CCW):
4 12 9
1 16 8
5 9 2

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

Xoay từng lớp vỏ (layer) từ ngoài vào trong. Với mỗi lớp, xoay 4 góc và các phần tử trên cạnh bằng cách đổi chỗ 4 phần tử cùng lúc.

Mã nguồn Naive

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

void rotateCCW(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}};
    rotateCCW(mat);
    cout << "Ma trận xoay 90° CCW:\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 hàng (Efficient)

Xoay 90° CCW = Chuyển vị (Transpose) + Đảo thứ tự hàng (Reverse rows).

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

Mã nguồn Efficient

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

void rotateCCW(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 rows
    for (int i = 0; i < N/2; i++)
        for (int j = 0; j < N; j++)
            swap(mat[i][j], mat[N-1-i][j]);
}

int main() {
    int mat[N][N] = {{5,1,4}, {9,16,12}, {2,8,9}};
    rotateCCW(mat);
    cout << "Ma trận xoay 90° CCW:\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)

4 12 9
1 16 8
5 9 2

Kết luận

Bài viết so sánh 2 cách xoay ma trận 90° CCW in-place: xoay theo vòng (phức tạp) và chuyển vị + đảo hàng (đơn giản, hiệu quả). Cách 2 khuyến nghị dùng. Mã C++ đầy đủ cho cả hai.