Bài 27.4: Bài tập thực hành ma trận xoắn ốc trong C++

Chào mừng bạn đến với bài viết tiếp theo trong series Khám phá Lập trình C++! Hôm nay, chúng ta sẽ cùng nhau chinh phục một bài toán khá thú vị và kinh điển liên quan đến ma trận (mảng 2 chiều) - bài toán điền ma trận theo hình xoắn ốc (Spiral Matrix). Đây là một bài tập thực hành tuyệt vời để củng cố kỹ năng xử lý mảng và phát triển tư duy thuật toán của bạn.

Bài Toán Ma Trận Xoắn Ốc là gì?

Bài toán đặt ra là: cho trước kích thước của một ma trận vuông N x N (hoặc tổng quát hơn là M x N), hãy điền các số nguyên liên tiếp từ 1 đến NN (hoặc MN) vào ma trận đó theo một đường đi hình xoắn ốc từ ngoài vào trong.

Ví dụ, với ma trận 3x3, kết quả mong muốn sẽ là:

1  2  3
8  9  4
7  6  5

Với ma trận 4x4:

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

Nghe có vẻ đơn giản, nhưng để viết code một cách chính xác và hiệu quả, chúng ta cần có một thuật toán rõ ràng.

Ý Tưởng Thuật Toán

Làm thế nào để mô phỏng đường đi "xoắn ốc" này bằng code? Hãy quan sát đường đi của các số trong ví dụ:

  • Chúng ta bắt đầu từ góc trên bên trái (0,0).
  • Điền các số theo hướng phải cho đến khi gặp biên.
  • Sau đó, chuyển hướng xuống dưới, điền các số theo hướng xuống cho đến khi gặp biên.
  • Tiếp theo, chuyển hướng sang trái, điền các số theo hướng trái cho đến khi gặp biên.
  • Cuối cùng, chuyển hướng lên trên, điền các số theo hướng lên cho đến khi gặp biên.

Sau khi hoàn thành một vòng (phải -> xuống -> trái -> lên), chúng ta đã điền được lớp "vỏ" ngoài cùng của hình xoắn ốc. Vùng chưa điền lúc này là một ma trận nhỏ hơn nằm bên trong. Chúng ta chỉ cần lặp lại quá trình tương tự với ma trận nhỏ hơn này cho đến khi toàn bộ ma trận được điền đầy.

Để quản lý các "biên" của ma trận nhỏ dần này, chúng ta có thể sử dụng bốn biến:

  • top: Chỉ số hàng trên cùng của vùng hiện tại.
  • bottom: Chỉ số hàng dưới cùng của vùng hiện tại.
  • left: Chỉ số cột bên trái nhất của vùng hiện tại.
  • right: Chỉ số cột bên phải nhất của vùng hiện tại.

Ban đầu, top = 0, bottom = N-1, left = 0, right = N-1 (hoặc M-1 và N-1 cho ma trận M x N). Sau mỗi khi hoàn thành một hướng di chuyển, chúng ta sẽ cập nhật một trong các biến biên này để "thu nhỏ" vùng làm việc lại.

Các Bước Thực Hiện Chi Tiết

  1. Khởi tạo một ma trận M x N với tất cả các phần tử bằng 0 (hoặc giá trị mặc định nào đó).
  2. Khởi tạo biến count = 1 (số sẽ điền vào ô tiếp theo).
  3. Khởi tạo top = 0, bottom = M-1, left = 0, right = N-1.
  4. Sử dụng một vòng lặp chính tiếp tục chạy miễn là top <= bottom và left <= right (điều kiện này đảm bảo vẫn còn vùng để điền).

  5. Bên trong vòng lặp chính, thực hiện 4 bước điền theo 4 hướng:

    • Điền từ trái sang phải (hàng top): Duyệt cột j từ left đến right. Điền matrix[top][j] = count++. Sau khi điền xong hàng này, tăng top lên 1 (top++) vì hàng trên cùng đã được xử lý.
    • Kiểm tra điều kiện thoát: Sau mỗi bước điền theo một hướng, quan trọng là phải kiểm tra lại điều kiện top <= bottom và left <= right. Nếu điều kiện này không còn đúng, tức là ma trận đã được điền đầy hoặc chỉ còn lại một hàng/cột đơn lẻ đã được xử lý ở bước trước đó, thoát khỏi vòng lặp chính.
    • Điền từ trên xuống dưới (cột right): Duyệt hàng i từ top đến bottom. Điền matrix[i][right] = count++. Sau khi điền xong cột này, giảm right đi 1 (right--).
    • Kiểm tra điều kiện thoát: Lại kiểm tra top <= bottom và left <= right.
    • Điền từ phải sang trái (hàng bottom): Duyệt cột j từ right xuống left. Điền matrix[bottom][j] = count++. Sau khi điền xong hàng này, giảm bottom đi 1 (bottom--).
    • Kiểm tra điều kiện thoát: Lại kiểm tra top <= bottom và left <= right.
    • Điền từ dưới lên trên (cột left): Duyệt hàng i từ bottom xuống top. Điền matrix[i][left] = count++. Sau khi điền xong cột này, tăng left lên 1 (left++).
    • Kiểm tra điều kiện thoát: Lại kiểm tra top <= bottom và left <= right.

  6. Khi vòng lặp chính kết thúc, ma trận đã được điền đầy đủ theo hình xoắn ốc.

Code Minh Họa (Ví dụ 1: Ma trận vuông)

Chúng ta sẽ sử dụng vector<vector<int>> để biểu diễn ma trận và cout để in kết quả. Để kết quả in ra thẳng hàng dễ nhìn, chúng ta có thể dùng thêm setw và fixed từ thư viện <iomanip>.

#include <iostream>
#include <vector>
#include <iomanip> // For setw and fixed

int main() {
    int n;
    cout << "Nhap kich thuoc ma tran vuong N: ";
    cin >> n;

    // Tao ma tran N x N va khoi tao tat ca phan tu bang 0
    vector<vector<int>> matrix(n, vector<int>(n, 0));

    int count = 1; // So bat dau dien
    int top = 0;
    int bottom = n - 1;
    int left = 0;
    int right = n - 1;

    // Vong lap chinh tiep tuc khi con vung de dien
    while (top <= bottom && left <= right) {
        // 1. Dien tu trai sang phai (Hang top)
        for (int j = left; j <= right; ++j) {
            matrix[top][j] = count++;
        }
        top++; // Tang top vi hang tren cung da xong

        // Kiem tra dieu kien sau khi tang top
        if (top > bottom || left > right) break;

        // 2. Dien tu tren xuong duoi (Cot right)
        for (int i = top; i <= bottom; ++i) {
            matrix[i][right] = count++;
        }
        right--; // Giam right vi cot ben phai da xong

        // Kiem tra dieu kien sau khi giam right
        if (top > bottom || left > right) break;

        // 3. Dien tu phai sang trai (Hang bottom)
        for (int j = right; j >= left; --j) {
            matrix[bottom][j] = count++;
        }
        bottom--; // Giam bottom vi hang duoi cung da xong

        // Kiem tra dieu kien sau khi giam bottom
        if (top > bottom || left > right) break;

        // 4. Dien tu duoi len tren (Cot left)
        for (int i = bottom; i >= top; --i) {
            matrix[i][left] = count++;
        }
        left++; // Tang left vi cot ben trai da xong

        // Kiem tra dieu kien sau khi tang left
        if (top > bottom || left > right) break;
    }

    // In ma tran ra man hinh
    cout << "\nMa tran xoan oc " << n << "x" << n << " la:\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            // Dung setw de can le va in so
            cout << setw(4) << matrix[i][j];
        }
        cout << endl; // Xuong dong sau moi hang
    }

    return 0;
}
Giải Thích Code (Ví dụ 1)
  • Chúng ta khai báo biến n để lấy kích thước ma trận vuông từ người dùng.
  • vector<vector<int>> matrix(n, vector<int>(n, 0)); tạo ra một ma trận n x n và khởi tạo tất cả các ô bằng 0. Đây là cách phổ biến để làm việc với mảng 2 chiều động trong C++.
  • Các biến count, top, bottom, left, right được khởi tạo như đã phân tích ở phần ý tưởng.
  • Vòng lặp while (top <= bottom && left <= right) là vòng lặp chính. Nó sẽ tiếp tục chạy cho đến khi các biên top vượt qua bottom hoặc left vượt qua right, điều này xảy ra khi toàn bộ ma trận đã được điền.
  • Bên trong vòng lặp while:
    • Vòng for đầu tiên điền từ left sang right trên hàng top. Sau đó, top được tăng lên để "cắt bỏ" hàng đã điền.
    • Rất quan trọng: Sau mỗi bước điền (phải, xuống, trái, lên), chúng ta kiểm tra lại điều kiện top <= bottom && left <= right (hoặc top > bottom || left > right để break). Điều này xử lý các trường hợp ma trận có kích thước lẻ (như 3x3, 5x5) nơi có thể còn lại một hàng hoặc một cột duy nhất ở trung tâm sau khi hoàn thành 3 hướng di chuyển.
    • Vòng for thứ hai điền từ top xuống bottom trên cột right. Sau đó, right được giảm đi.
    • Vòng for thứ ba điền từ right sang left trên hàng bottom. Sau đó, bottom được giảm đi.
    • Vòng for cuối cùng điền từ bottom lên top trên cột left. Sau đó, left được tăng lên.
  • Sau vòng lặp while, ma trận đã được điền. Chúng ta dùng hai vòng lặp for lồng nhau để duyệt và in ma trận ra màn hình. setw(4) đảm bảo mỗi số chiếm ít nhất 4 ký tự, giúp các cột thẳng hàng kể cả khi số có 1 hoặc 2 chữ số.

Code Minh Họa (Ví dụ 2: Ma trận chữ nhật)

Thuật toán boundary-shrinking hoạt động tốt cho cả ma trận chữ nhật M x N. Chúng ta chỉ cần thay đổi cách khởi tạo kích thước và các biến biên ban đầu.

#include <iostream>
#include <vector>
#include <iomanip> // For setw and fixed

int main() {
    int m, n;
    cout << "Nhap so hang M: ";
    cin >> m;
    cout << "Nhap so cot N: ";
    cin >> n;

    // Tao ma tran M x N
    vector<vector<int>> matrix(m, vector<int>(n, 0));

    int count = 1; // So bat dau dien
    int top = 0;
    int bottom = m - 1;
    int left = 0;
    int right = n - 1;

    // Vong lap chinh tiep tuc khi con vung de dien
    while (top <= bottom && left <= right) {
        // 1. Dien tu trai sang phai (Hang top)
        for (int j = left; j <= right; ++j) {
            matrix[top][j] = count++;
        }
        top++; // Tang top vi hang tren cung da xong

        // Kiem tra dieu kien sau khi tang top
        if (top > bottom || left > right) break;

        // 2. Dien tu tren xuong duoi (Cot right)
        for (int i = top; i <= bottom; ++i) {
            matrix[i][right] = count++;
        }
        right--; // Giam right vi cot ben phai da xong

        // Kiem tra dieu kien sau khi giam right
        if (top > bottom || left > right) break;

        // 3. Dien tu phai sang trai (Hang bottom)
        for (int j = right; j >= left; --j) {
            matrix[bottom][j] = count++;
        }
        bottom--; // Giam bottom vi hang duoi cung da xong

        // Kiem tra dieu kien sau khi giam bottom
        if (top > bottom || left > right) break;

        // 4. Dien tu duoi len tren (Cot left)
        for (int i = bottom; i >= top; --i) {
            matrix[i][left] = count++;
        }
        left++; // Tang left vi cot ben trai da xong

        // Kiem tra dieu kien sau khi tang left
        if (top > bottom || left > right) break;
    }

    // In ma tran ra man hinh
    cout << "\nMa tran xoan oc " << m << "x" << n << " la:\n";
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
             cout << setw(4) << matrix[i][j];
        }
        cout << endl; // Xuong dong sau moi hang
    }

    return 0;
}
Giải Thích Code (Ví dụ 2)

Code cho ma trận chữ nhật gần như y hệt code cho ma trận vuông. Sự khác biệt chính là:

  • Chúng ta đọc vào hai biến m và n cho số hàng và số cột.
  • Khi khởi tạo ma trận: vector<vector<int>> matrix(m, vector<int>(n, 0));.
  • Khi khởi tạo các biên: bottom = m - 1; và right = n - 1;.

Logic thuật toán điền theo 4 hướng và cập nhật biên vẫn hoàn toàn áp dụng được cho ma trận chữ nhật, làm nổi bật tính tổng quát của phương pháp này.

Lưu Ý và Mở Rộng

  • Điều kiện kiểm tra if (top > bottom || left > right) break; sau mỗi vòng for là cực kỳ quan trọng, đặc biệt với ma trận có một chiều là 1 (ví dụ 1x5, 5x1) hoặc ma trận có kích thước lẻ. Nó đảm bảo rằng chúng ta không cố gắng truy cập vào các vị trí ngoài giới hạn hoặc điền đè lên các ô đã điền khi vùng còn lại chỉ là một hàng hoặc một cột đơn.
  • Bài toán ma trận xoắn ốc còn có một biến thể khác là duyệt ma trận xoắn ốc (cho trước một ma trận đã điền, hãy in ra các phần tử theo thứ tự xoắn ốc). Thuật toán sử dụng 4 biên và 4 hướng di chuyển tương tự, chỉ khác là thay vì điền số, chúng ta chỉ cần truy cập và in ra giá trị của phần tử.

Comments

There are no comments at the moment.