Bài 26.2: Ma trận xoắn ốc trong C++

Chào mừng các bạn quay trở lại với series blog về C++! Hôm nay chúng ta sẽ cùng nhau khám phá một bài toán khá thú vị và kinh điển trong lập trình: tạo ra Ma trận xoắn ốc (Spiral Matrix). Đây là một bài toán hay giúp chúng ta rèn luyện tư duy xử lý mảng hai chiều và logic điều hướng.

Ma Trận Xoắn Ốc Là Gì?

Một ma trận xoắn ốc là một ma trận vuông n x n (hoặc đôi khi là m x n) trong đó các phần tử được điền vào theo một đường xoắn ốc, bắt đầu từ góc trên bên trái và di chuyển vào phía trung tâm.

Ví dụ, một ma trận xoắn ốc 3x3 sẽ trông như thế này:

1  2  3
8  9  4
7  6  5

Và một ma trận xoắn ốc 4x4:

 1  2  3  4
12 13 14  5
11 16 15  6
10  9  8  7

Mục tiêu của chúng ta trong bài này là viết một chương trình C++ để tạo ra ma trận này cho một kích thước n bất kỳ.

Ý Tưởng Thuật Toán

Làm thế nào để điền các số từ 1 đến n*n vào ma trận theo hình xoắn ốc? Ý tưởng chính là mô phỏng quá trình "xoắn ốc" bằng cách di chuyển theo bốn hướng: phải, xuống, trái, và lên, sau đó thu hẹp ranh giới của ma trận sau mỗi lần di chuyển hoàn tất một "lớp" của xoắn ốc.

Chúng ta sẽ duy trì bốn biến để theo dõi ranh giới hiện tại của khu vực chưa điền trong ma trận:

  • top: chỉ số hàng trên cùng
  • bottom: chỉ số hàng dưới cùng
  • left: chỉ số cột bên trái nhất
  • right: chỉ số cột bên phải nhất

Ban đầu, top và left sẽ là 0, còn bottom và right sẽ là n-1. Chúng ta sẽ điền các số theo trình tự và điều chỉnh các ranh giới này cho đến khi top vượt quá bottom hoặc left vượt quá right, báo hiệu rằng toàn bộ ma trận đã được điền đầy.

Các bước di chuyển sẽ là:

  1. Điền từ trái sang phải: Điền vào hàng top từ cột left đến right. Sau khi hoàn thành, tăng top lên 1 (để loại bỏ hàng trên cùng đã điền).
  2. Điền từ trên xuống dưới: Điền vào cột right từ hàng top đến bottom. Sau khi hoàn thành, giảm right xuống 1 (để loại bỏ cột bên phải đã điền).
  3. Điền từ phải sang trái: Điền vào hàng bottom từ cột right về left. Sau khi hoàn thành, giảm bottom xuống 1 (để loại bỏ hàng dưới cùng đã điền).
  4. Điền từ dưới lên trên: Điền vào cột left từ hàng bottom về top. Sau khi hoàn thành, tăng left lên 1 (để loại bỏ cột bên trái đã điền).

Chúng ta lặp lại chu trình này cho đến khi các ranh giới gặp nhau hoặc vượt qua nhau.

Lưu ý quan trọng: Sau mỗi lần di chuyển theo một hướng (trừ hướng đầu tiên), chúng ta cần kiểm tra xem các ranh giới top và bottom, hoặc left và right đã gặp nhau hoặc vượt qua nhau chưa. Nếu có, điều đó có nghĩa là không còn khu vực hợp lệ nào để điền nữa, và chúng ta phải dừng lại ngay lập tức để tránh điền đè hoặc điền sai.

Triển Khai Bằng C++

Bây giờ, chúng ta hãy chuyển ý tưởng này thành code C++. Chúng ta sẽ sử dụng vector<vector<int>> để biểu diễn ma trận.

Đầu tiên, cần các thư viện cơ bản: iostream cho nhập xuất và vector cho ma trận động.

#include <iostream>
#include <vector>

// Hàm để tạo ma trận xoắn ốc kích thước n x n
vector<vector<int>> generateSpiralMatrix(int n) {
    // Xử lý trường hợp n = 0
    if (n <= 0) {
        return {}; // Trả về ma trận rỗng
    }

    // Khởi tạo ma trận n x n với giá trị 0
    vector<vector<int>> matrix(n, vector<int>(n, 0));

    // Khởi tạo các biến ranh giới và giá trị hiện tại
    int top = 0;
    int bottom = n - 1;
    int left = 0;
    int right = n - 1;
    int currentValue = 1; // Giá trị bắt đầu điền

    // Lặp cho đến khi các ranh giới gặp nhau hoặc vượt qua
    while (top <= bottom && left <= right) {
        // 1. Điền từ trái sang phải (hàng top)
        for (int col = left; col <= right; ++col) {
            matrix[top][col] = currentValue++;
        }
        top++; // Tăng top để bỏ qua hàng trên cùng đã điền

        // Kiểm tra xem còn khu vực hợp lệ để điền tiếp không
        if (top > bottom) break;

        // 2. Điền từ trên xuống dưới (cột right)
        for (int row = top; row <= bottom; ++row) {
            matrix[row][right] = currentValue++;
        }
        right--; // Giảm right để bỏ qua cột bên phải đã điền

        // Kiểm tra xem còn khu vực hợp lệ để điền tiếp không
        if (left > right) break;

        // 3. Điền từ phải sang trái (hàng bottom)
        for (int col = right; col >= left; --col) {
            matrix[bottom][col] = currentValue++;
        }
        bottom--; // Giảm bottom để bỏ qua hàng dưới cùng đã điền

        // Kiểm tra xem còn khu vực hợp lệ để điền tiếp không
        if (top > bottom) break;

        // 4. Điền từ dưới lên trên (cột left)
        for (int row = bottom; row >= top; --row) {
            matrix[row][left] = currentValue++;
        }
        left++; // Tăng left để bỏ qua cột bên trái đã điền

        // Kiểm tra xem còn khu vực hợp lệ để điền tiếp không (không thực sự cần ở đây
        // vì vòng lặp while sẽ kiểm tra ở lần lặp tiếp theo, nhưng có thể thêm
        // để đảm bảo logic nhất quán)
        if (left > right) break;
    }

    return matrix;
}

// Hàm trợ giúp để in ma trận ra màn hình
void printMatrix(const vector<vector<int>>& matrix) {
    if (matrix.empty()) {
        cout << "Ma tran rong." << endl;
        return;
    }
    for (const auto& row : matrix) {
        for (int val : row) {
            // Định dạng để các số thẳng cột
            cout.width(4); // Đặt chiều rộng cố định cho mỗi số
            cout << right << val; // Căn phải
        }
        cout << endl;
    }
}

Giải thích Code:

  1. #include <iostream> và #include <vector>: Nhập các thư viện cần thiết.
  2. generateSpiralMatrix(int n): Hàm chính nhận kích thước n và trả về ma trận n x n.
  3. if (n <= 0) return {};: Xử lý trường hợp đầu vào không hợp lệ hoặc ma trận rỗng.
  4. vector<vector<int>> matrix(n, vector<int>(n, 0));: Khởi tạo ma trận 2 chiều kích thước n x n. vector<int>(n, 0) tạo ra một hàng gồm n số 0, và vector<vector<int>>(n, ...) tạo ra n hàng như vậy.
  5. int top = 0, bottom = n - 1, left = 0, right = n - 1;: Khởi tạo các chỉ số ranh giới cho ma trận.
  6. int currentValue = 1;: Biến để theo dõi số tiếp theo cần điền vào ma trận, bắt đầu từ 1.
  7. while (top <= bottom && left <= right): Vòng lặp chính tiếp tục miễn là còn khu vực hợp lệ (các ranh giới chưa vượt qua nhau).
  8. for (int col = left; col <= right; ++col): Vòng lặp điền hàng trên cùng từ trái sang phải.
    • matrix[top][col] = currentValue++;: Điền currentValue vào ô (top, col) và sau đó tăng currentValue.
  9. top++;: Sau khi điền xong hàng top, tăng top lên để bắt đầu lớp xoắn ốc tiếp theo từ hàng dưới hơn.
  10. if (top > bottom) break;: Quan trọng! Kiểm tra sau khi di chuyển ranh giới top. Nếu top đã vượt quá bottom, có nghĩa là không còn hàng nào trong khu vực hiện tại, và chúng ta phải dừng lại. Điều này xử lý các trường hợp ma trận có kích thước lẻ hoặc khi chỉ còn một hàng duy nhất ở giữa.
  11. Ba khối for và điều chỉnh ranh giới còn lại: Tương tự, các khối tiếp theo điền cột phải, hàng dưới và cột trái, điều chỉnh các ranh giới right, bottom, left tương ứng sau mỗi lần điền.
  12. Các kiểm tra if (left > right) break; và if (top > bottom) break;: Các kiểm tra này được đặt sau mỗi vòng for (trừ vòng đầu tiên) để đảm bảo dừng lại ngay khi các ranh giới gặp nhau. Ví dụ, sau khi điền xong cột right và giảm right, nếu left đã vượt qua right, có nghĩa là không còn cột nào trong khu vực hiện tại. Điều này xử lý các trường hợp ma trận có kích thước lẻ hoặc khi chỉ còn một cột duy nhất ở giữa.
  13. return matrix;: Trả về ma trận đã điền.
  14. printMatrix(...): Hàm trợ giúp để in ma trận ra console một cách dễ đọc. Nó sử dụng cout.width(4) và right để căn chỉnh các số, giúp ma trận hiển thị đẹp hơn.
Ví Dụ Sử Dụng

Bây giờ, chúng ta hãy sử dụng hàm generateSpiralMatrix trong hàm main để tạo và in ra ma trận xoắn ốc với các kích thước khác nhau.

int main() {
    cout << "Ma tran xoan oc 3x3:" << endl;
    vector<vector<int>> matrix3x3 = generateSpiralMatrix(3);
    printMatrix(matrix3x3);
    cout << endl; // In dòng trống cho dễ nhìn

    cout << "Ma tran xoan oc 4x4:" << endl;
    vector<vector<int>> matrix4x4 = generateSpiralMatrix(4);
    printMatrix(matrix4x4);
    cout << endl;

    cout << "Ma tran xoan oc 1x1:" << endl;
    vector<vector<int>> matrix1x1 = generateSpiralMatrix(1);
    printMatrix(matrix1x1);
    cout << endl;

     cout << "Ma tran xoan oc 0x0:" << endl;
    vector<vector<int>> matrix0x0 = generateSpiralMatrix(0);
    printMatrix(matrix0x0);
    cout << endl;

    return 0;
}

Giải thích Ví Dụ:

  • Chúng ta gọi generateSpiralMatrix với các kích thước 3, 4, 1, và 0.
  • Kết quả trả về là một vector<vector<int>> chứa ma trận.
  • Hàm printMatrix được gọi để hiển thị nội dung của ma trận lên màn hình.

Output Khi Chạy Chương Trình:

Ma tran xoan oc 3x3:
   1   2   3
   8   9   4
   7   6   5

Ma tran xoan oc 4x4:
   1   2   3   4
  12  13  14   5
  11  16  15   6
  10   9   8   7

Ma tran xoan oc 1x1:
   1

Ma tran xoan oc 0x0:
Ma tran rong.

Comments

There are no comments at the moment.