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>
#include <iomanip>

vector<vector<int>> taoMxXoanOc(int sz) {
    if (sz <= 0) {
        return {};
    }

    vector<vector<int>> mt(sz, vector<int>(sz, 0));

    int t = 0;
    int b = sz - 1;
    int l = 0;
    int r = sz - 1;
    int cnt = 1;

    while (t <= b && l <= r) {
        for (int j = l; j <= r; ++j) {
            mt[t][j] = cnt++;
        }
        t++;

        if (t > b) break;

        for (int i = t; i <= b; ++i) {
            mt[i][r] = cnt++;
        }
        r--;

        if (l > r) break;

        for (int j = r; j >= l; --j) {
            mt[b][j] = cnt++;
        }
        b--;

        if (t > b) break;

        for (int i = b; i >= t; --i) {
            mt[i][l] = cnt++;
        }
        l++;
    }

    return mt;
}

void inMx(const vector<vector<int>>& mt) {
    if (mt.empty()) {
        cout << "Ma tran rong." << endl;
        return;
    }
    for (const auto& dong : mt) {
        for (int gt : dong) {
            cout << setw(4) << right << gt;
        }
        cout << endl;
    }
}

Giải thích Code:

  1. #include <iostream>, #include <vector> và #include <iomanip>: Nhập các thư viện cần thiết.
  2. taoMxXoanOc(int sz): Hàm chính nhận kích thước sz và trả về ma trận sz x sz.
  3. if (sz <= 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>> mt(sz, vector<int>(sz, 0));: Khởi tạo ma trận 2 chiều kích thước sz x sz. vector<int>(sz, 0) tạo ra một hàng gồm sz số 0, và vector<vector<int>>(sz, ...) tạo ra sz hàng như vậy.
  5. int t = 0, b = sz - 1, l = 0, r = sz - 1;: Khởi tạo các chỉ số ranh giới cho ma trận.
  6. int cnt = 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 (t <= b && l <= r): 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 j = l; j <= r; ++j): Vòng lặp điền hàng trên cùng từ trái sang phải.
    • mt[t][j] = cnt++;: Điền cnt vào ô (t, j) và sau đó tăng cnt.
  9. t++;: Sau khi điền xong hàng t, tăng t lên để bắt đầu lớp xoắn ốc tiếp theo từ hàng dưới hơn.
  10. if (t > b) break;: Quan trọng! Kiểm tra sau khi di chuyển ranh giới t. Nếu t đã vượt quá b, 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 r, b, l tương ứng sau mỗi lần điền.
  12. Các kiểm tra if (l > r) break; và if (t > b) 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 r và giảm r, nếu l đã vượt qua r, 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 mt;: Trả về ma trận đã điền.
  14. inMx(...): Hàm trợ giúp để in ma trận ra console một cách dễ đọc. Nó sử dụng setw(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 taoMxXoanOc 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>> mx3 = taoMxXoanOc(3);
    inMx(mx3);
    cout << endl;

    cout << "Ma tran xoan oc 4x4:" << endl;
    vector<vector<int>> mx4 = taoMxXoanOc(4);
    inMx(mx4);
    cout << endl;

    cout << "Ma tran xoan oc 1x1:" << endl;
    vector<vector<int>> mx1 = taoMxXoanOc(1);
    inMx(mx1);
    cout << endl;

    cout << "Ma tran xoan oc 0x0:" << endl;
    vector<vector<int>> mx0 = taoMxXoanOc(0);
    inMx(mx0);
    cout << endl;

    return 0;
}

Giải thích Ví Dụ:

  • Chúng ta gọi taoMxXoanOc 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 inMx đượ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.