Bài 9.3. Mảng xoắn ốc và các biến thể

Chào mừng trở lại với series blog về Cấu trúc dữ liệu và Giải thuật!

Trong những bài trước, chúng ta đã khám phá nhiều loại cấu trúc dữ liệu cơ bản và nâng cao. Hôm nay, chúng ta sẽ đi sâu vào một chủ đề khá thú vị và thường gặp trong các bài toán lập trình cũng như phỏng vấn: Mảng xoắn ốc (Spiral Matrix). Mặc dù không phải là một cấu trúc dữ liệu độc lập như danh sách liên kết hay cây, nhưng cách thao tác và xử lý với mảng xoắn ốc lại là một bài tập tuyệt vời để rèn luyện kỹ năng làm việc với mảng 2 chiều và tư duy giải thuật theo các biên (boundaries).

Mảng xoắn ốc là gì?

Đúng như tên gọi, một mảng xoắn ốc là một mảng 2 chiều (ma trận) mà các phần tử của nó được điền hoặc đọc theo một lộ trình xoắn ốc, bắt đầu từ góc trên bên trái (hoặc một điểm khác) và di chuyển vào trung tâm.

Hãy tưởng tượng một ma trận kích thước 3x3:

1  2  3
8  9  4
7  6  5

Thứ tự đọc các phần tử theo xoắn ốc sẽ là: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9.

Hoặc một ma trận 4x4:

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

Thứ tự đọc: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16.

Các bài toán liên quan đến mảng xoắn ốc thường xoay quanh hai vấn đề chính:

Tạo mảng xoắn ốc: Điền các giá trị vào một ma trận rỗng theo thứ tự xoắn ốc.
Duyệt mảng xoắn ốc: Đọc hoặc xử lý các phần tử của một ma trận đã có theo thứ tự xoắn ốc.

Chúng ta sẽ lần lượt đi qua từng bài toán này.

Bài toán 1: Tạo mảng xoắn ốc (Generating a Spiral Matrix)

Yêu cầu: Cho hai số nguyên dương m và n, tạo ra một ma trận kích thước m x n chứa các số nguyên từ 1 đến m*n theo thứ tự xoắn ốc.

Ý tưởng giải thuật:

Để tạo một mảng xoắn ốc, chúng ta có thể mô phỏng quá trình điền số theo từng lớp của vòng xoắn ốc, từ ngoài vào trong. Chúng ta cần theo dõi các biên hiện tại của vùng chưa được điền vào. Các biên này sẽ co lại sau mỗi khi chúng ta hoàn thành một lượt điền theo một hướng (phải, xuống, trái, lên).

Chúng ta sẽ cần 4 biến để đại diện cho các 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 = m - 1, left = 0, right = n - 1. Chúng ta cũng cần một biến value để lưu trữ số sẽ điền tiếp theo, khởi tạo bằng 1.

Quá trình điền sẽ lặp lại cho đến khi top > bottom hoặc left > right (nghĩa là vùng hiện tại không còn hợp lệ hoặc đã được điền hết). Trong mỗi lần lặp:

Điền từ trái sang phải: Điền các số vào hàng top, từ cột left đến right. Sau khi xong, tăng top lên 1 để loại bỏ hàng này khỏi vùng chưa điền.
Điền từ trên xuống dưới: Điền các số vào cột right, từ hàng top đến bottom. Sau khi xong, giảm right xuống 1 để loại bỏ cột này.
Điền từ phải sang trái: (Chỉ thực hiện nếu top <= bottom - điều kiện này quan trọng cho ma trận hình chữ nhật để tránh điền trùng hoặc điền vào vùng đã xử lý). Điền các số vào hàng bottom, từ cột right xuống left. Sau khi xong, giảm bottom xuống 1.
Điền từ dưới lên trên: (Chỉ thực hiện nếu left <= right - điều kiện này quan trọng cho ma trận hình chữ nhật). Điền các số vào cột left, từ hàng bottom xuống top. Sau khi xong, tăng left lên 1.

Cứ như vậy, các biên co lại, và chúng ta điền số vào lớp tiếp theo của vòng xoắn ốc.

Code minh họa bằng C++:

Chúng ta sẽ sử dụng std::vector<std::vector<int>> để biểu diễn ma trận.

#include <vector>
#include <iostream>

std::vector<std::vector<int>> generateSpiralMatrix(int m, int n) {
    if (m <= 0 || n <= 0) {
        return {}; // Trả về ma trận rỗng nếu kích thước không hợp lệ
    }

    // Khởi tạo ma trận kích thước m x n với các giá trị mặc định
    std::vector<std::vector<int>> matrix(m, std::vector<int>(n));

    int top = 0;         // Chỉ số hàng trên cùng
    int bottom = m - 1;  // Chỉ số hàng dưới cùng
    int left = 0;        // Chỉ số cột bên trái nhất
    int right = n - 1;   // Chỉ số cột bên phải nhất

    int value = 1;       // Giá trị sẽ điền vào ô tiếp theo

    // Lặp cho đến khi các biên gặp nhau hoặc vượt qua nhau
    while (top <= bottom && left <= right) {

        // 1. Điền từ trái sang phải (hàng top)
        for (int c = left; c <= right; ++c) {
            matrix[top][c] = value++;
        }
        top++; // Tăng top, loại bỏ hàng trên cùng

        // Kiểm tra điều kiện để tránh điền trùng hoặc lỗi trong trường hợp ma trận chỉ có 1 hàng
        if (top > bottom) break;

        // 2. Điền từ trên xuống dưới (cột right)
        for (int r = top; r <= bottom; ++r) {
            matrix[r][right] = value++;
        }
        right--; // Giảm right, loại bỏ cột phải

        // Kiểm tra điều kiện để tránh điền trùng hoặc lỗi trong trường hợp ma trận chỉ có 1 cột
        if (left > right) break;

        // 3. Điền từ phải sang trái (hàng bottom)
        for (int c = right; c >= left; --c) {
            matrix[bottom][c] = value++;
        }
        bottom--; // Giảm bottom, loại bỏ hàng dưới

        // Kiểm tra điều kiện tương tự
        if (top > bottom) break;

        // 4. Điền từ dưới lên trên (cột left)
        for (int r = bottom; r >= top; --r) {
            matrix[r][left] = value++;
        }
        left++; // Tăng left, loại bỏ cột trái

         // Kiểm tra điều kiện tương tự
        if (left > right) break;
    }

    return matrix;
}

// Hàm trợ giúp để in ma trận (cho mục đích minh họa)
void printMatrix(const std::vector<std::vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int val : row) {
            std::cout << val << "\t"; // Dùng tab để căn chỉnh
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

int main() {
    std::cout << "Ma tran xoan oc 3x4:" << std::endl;
    std::vector<std::vector<int>> spiral3x4 = generateSpiralMatrix(3, 4);
    printMatrix(spiral3x4);

    std::cout << "Ma tran xoan oc 5x5:" << std::endl;
    std::vector<std::vector<int>> spiral5x5 = generateSpiralMatrix(5, 5);
    printMatrix(spiral5x5);

     std::cout << "Ma tran xoan oc 1x5:" << std::endl;
    std::vector<std::vector<int>> spiral1x5 = generateSpiralMatrix(1, 5);
    printMatrix(spiral1x5);

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


    return 0;
}

Giải thích code:

generateSpiralMatrix(int m, int n): Hàm này nhận kích thước m (số hàng) và n (số cột) làm đầu vào.
std::vector<std::vector<int>> matrix(m, std::vector<int>(n));: Tạo một ma trận m x n rỗng.
Các biến top, bottom, left, right được khởi tạo để bao trọn ma trận ban đầu.
Biến value bắt đầu từ 1, sẽ tăng dần khi điền vào ma trận.
Vòng lặp while (top <= bottom && left <= right): Lặp cho đến khi không còn vùng hợp lệ để điền (các biên đã đi qua nhau).
Bên trong vòng lặp, có 4 vòng for tương ứng với 4 hướng điền:
- Vòng for đầu tiên: Duyệt cột từ left đến right tại hàng top, điền value++. Sau đó top tăng.
- Vòng for thứ hai: Duyệt hàng từ top đến bottom tại cột right, điền value++. Sau đó right giảm.
- Vòng for thứ ba: Duyệt cột từ right về left tại hàng bottom, điền value++. Sau đó bottom giảm. Quan trọng: Cần kiểm tra top <= bottom trước khi thực hiện vòng lặp này. Nếu top > bottom (ví dụ: ma trận chỉ có 1 hàng), hàng bottom đã bị loại bỏ sau bước 1, nên không cần điền theo hướng này nữa.
- Vòng for thứ tư: Duyệt hàng từ bottom về top tại cột left, điền value++. Sau đó left tăng. Quan trọng: Cần kiểm tra left <= right trước khi thực hiện vòng lặp này. Nếu left > right (ví dụ: ma trận chỉ có 1 cột), cột left đã bị loại bỏ sau bước 2, nên không cần điền theo hướng này nữa.
Sau mỗi bước điền theo một hướng, chúng ta cập nhật biên tương ứng và ngay lập tức kiểm tra điều kiện top <= bottom hoặc left <= right để break khỏi vòng lặp while chính nếu vùng còn lại đã hết. Điều này xử lý chính xác các trường hợp ma trận có số hàng hoặc số cột lẻ, nơi vòng xoắn ốc kết thúc ở một hàng hoặc một cột duy nhất ở trung tâm.
Hàm printMatrix được thêm vào để dễ dàng hiển thị kết quả.
main function minh họa cách sử dụng hàm generateSpiralMatrix với các kích thước ma trận khác nhau.

Độ phức tạp thời gian của giải thuật này là O(mn) vì chúng ta thăm và điền vào mỗi ô của ma trận đúng một lần. Độ phức tạp không gian là O(mn) để lưu trữ ma trận kết quả.

Bài toán 2: Duyệt mảng xoắn ốc (Traversing a Spiral Matrix)

Yêu cầu: Cho một ma trận kích thước m x n, trả về danh sách các phần tử của ma trận theo thứ tự xoắn ốc.

Ý tưởng giải thuật:

Bài toán này có ý tưởng rất giống với việc tạo mảng xoắn ốc. Thay vì điền giá trị vào các ô, chúng ta sẽ đọc giá trị từ các ô và thêm chúng vào một danh sách kết quả (ví dụ: một std::vector trong C++).

Chúng ta vẫn sử dụng 4 biến top, bottom, left, right để theo dõi các biên của vùng chưa được duyệt. Quá trình duyệt cũng lặp lại cho đến khi các biên gặp nhau hoặc vượt qua nhau.

Trong mỗi lần lặp:

Duyệt từ trái sang phải: Đọc các phần tử tại hàng top, từ cột left đến right, thêm vào danh sách kết quả. Tăng top.
Duyệt từ trên xuống dưới: Đọc các phần tử tại cột right, từ hàng top đến bottom, thêm vào danh sách kết quả. Giảm right.
Duyệt từ phải sang trái: (Kiểm tra top <= bottom). Đọc các phần tử tại hàng bottom, từ cột right xuống left, thêm vào danh sách kết quả. Giảm bottom.
Duyệt từ dưới lên trên: (Kiểm tra left <= right). Đọc các phần tử tại cột left, từ hàng bottom xuống top, thêm vào danh sách kết quả. Tăng left.

Cứ như vậy, chúng ta thu thập các phần tử theo từng lớp của vòng xoắn ốc.

Code minh họa bằng C++:

#include <vector>
#include <iostream>
#include <vector> // Bao gồm thêm để dùng std::vector

std::vector<int> traverseSpiralMatrix(const std::vector<std::vector<int>>& matrix) {
    std::vector<int> result; // Danh sách lưu kết quả

    if (matrix.empty() || matrix[0].empty()) {
        return result; // Trả về danh sách rỗng nếu ma trận rỗng
    }

    int m = matrix.size();    // Số hàng
    int n = matrix[0].size(); // Số cột

    int top = 0;         // Chỉ số hàng trên cùng
    int bottom = m - 1;  // Chỉ số hàng dưới cùng
    int left = 0;        // Chỉ số cột bên trái nhất
    int right = n - 1;   // Chỉ số cột bên phải nhất

    // Lặp cho đến khi các biên gặp nhau hoặc vượt qua nhau
    while (top <= bottom && left <= right) {

        // 1. Duyệt từ trái sang phải (hàng top)
        for (int c = left; c <= right; ++c) {
            result.push_back(matrix[top][c]);
        }
        top++; // Tăng top, loại bỏ hàng trên cùng

        // Kiểm tra điều kiện để tránh duyệt trùng hoặc lỗi
        if (top > bottom) break;

        // 2. Duyệt từ trên xuống dưới (cột right)
        for (int r = top; r <= bottom; ++r) {
            result.push_back(matrix[r][right]);
        }
        right--; // Giảm right, loại bỏ cột phải

        // Kiểm tra điều kiện để tránh duyệt trùng hoặc lỗi
        if (left > right) break;

        // 3. Duyệt từ phải sang trái (hàng bottom)
        for (int c = right; c >= left; --c) {
            result.push_back(matrix[bottom][c]);
        }
        bottom--; // Giảm bottom, loại bỏ hàng dưới

        // Kiểm tra điều kiện tương tự
        if (top > bottom) break;

        // 4. Duyệt từ dưới lên trên (cột left)
        for (int r = bottom; r >= top; --r) {
            result.push_back(matrix[r][left]);
        }
        left++; // Tăng left, loại bỏ cột trái

        // Kiểm tra điều kiện tương tự
        if (left > right) break;
    }

    return result;
}

int main() {
    std::vector<std::vector<int>> matrix1 = {
        {1, 2, 3},
        {8, 9, 4},
        {7, 6, 5}
    };
    std::cout << "Duyet ma tran:" << std::endl;
    // Sử dụng hàm printMatrix từ ví dụ trước hoặc tự in kết quả
    printMatrix(matrix1); // Giả sử printMatrix đã được định nghĩa hoặc đưa vào đây

    std::vector<int> spiralOrder1 = traverseSpiralMatrix(matrix1);
    std::cout << "Ket qua duyet xoan oc: ";
    for (int val : spiralOrder1) {
        std::cout << val << " ";
    }
    std::cout << std::endl << std::endl;

    std::vector<std::vector<int>> matrix2 = {
        { 1,  2,  3,  4},
        {12, 13, 14,  5},
        {11, 16, 15,  6},
        {10,  9,  8,  7}
    };
    std::cout << "Duyet ma tran:" << std::endl;
    printMatrix(matrix2);

    std::vector<int> spiralOrder2 = traverseSpiralMatrix(matrix2);
    std::cout << "Ket qua duyet xoan oc: ";
    for (int val : spiralOrder2) {
        std::cout << val << " ";
    }
    std::cout << std::endl << std::endl;

     std::vector<std::vector<int>> matrix3 = {{1, 2, 3, 4, 5}}; // Ma tran 1x5
    std::cout << "Duyet ma tran 1x5:" << std::endl;
    printMatrix(matrix3);
    std::vector<int> spiralOrder3 = traverseSpiralMatrix(matrix3);
    std::cout << "Ket qua duyet xoan oc: ";
    for (int val : spiralOrder3) {
        std::cout << val << " ";
    }
    std::cout << std::endl << std::endl;

    std::vector<std::vector<int>> matrix4 = {{1}, {2}, {3}, {4}, {5}}; // Ma tran 5x1
    std::cout << "Duyet ma tran 5x1:" << std::endl;
    printMatrix(matrix4);
    std::vector<int> spiralOrder4 = traverseSpiralMatrix(matrix4);
    std::cout << "Ket qua duyet xoan oc: ";
    for (int val : spiralOrder4) {
        std::cout << val << " ";
    }
    std::cout << std::endl << std::endl;


    return 0;
}

Giải thích code:

traverseSpiralMatrix(const std::vector<std::vector<int>>& matrix): Hàm này nhận một ma trận (const để không sửa đổi ma trận gốc) và trả về một std::vector<int> chứa các phần tử theo thứ tự xoắn ốc.
std::vector<int> result;: Khởi tạo một vector rỗng để lưu trữ kết quả.
Kiểm tra ma trận rỗng.
Lấy kích thước m và n.
Các biến top, bottom, left, right và vòng lặp while có vai trò và logic tương tự như bài toán tạo mảng xoắn ốc.
Sự khác biệt chính nằm trong các vòng for: Thay vì gán giá trị (matrix[...][...] = value++), chúng ta đọc giá trị (result.push_back(matrix[...][...])) và thêm nó vào vector result.
Các kiểm tra if (top > bottom) break; và if (left > right) break; vẫn cần thiết để xử lý đúng các trường hợp ma trận hình chữ nhật hoặc ma trận đơn hàng/đơn cột.
Hàm main minh họa cách gọi hàm traverseSpiralMatrix và in kết quả.

Tương tự, độ phức tạp thời gian là O(mn) vì mỗi phần tử được đọc đúng một lần. Độ phức tạp không gian là O(mn) để lưu trữ ma trận đầu vào (nếu không tính ma trận đầu vào, thì là O(m*n) cho vector kết quả).

Các biến thể

Ý tưởng cốt lõi của việc sử dụng các biên co lại và di chuyển theo 4 hướng (phải, xuống, trái, lên) là cực kỳ linh hoạt. Nó có thể được áp dụng cho nhiều biến thể khác của bài toán mảng xoắn ốc:

Bắt đầu từ vị trí khác: Thay vì góc trên bên trái, bạn có thể bắt đầu từ góc dưới bên phải, hoặc trung tâm (đối với ma trận kích thước lẻ), và điều chỉnh hướng di chuyển ban đầu cùng logic cập nhật biên.
Điền theo quy luật khác: Thay vì điền số tăng dần 1, 2, 3..., bạn có thể điền các ký tự, các giá trị tính toán được, hoặc các phần tử từ một danh sách cho trước theo thứ tự xoắn ốc.
Duyệt ngược: Đọc các phần tử theo thứ tự xoắn ốc ngược lại (từ trong ra ngoài hoặc theo chiều kim đồng hồ ngược). Điều này yêu cầu điều chỉnh thứ tự xử lý các hướng trong vòng lặp.
Tìm kiếm phần tử: Mặc dù không phải là cách hiệu quả nhất để tìm kiếm trong ma trận nói chung, nhưng nếu biết rằng ma trận được điền theo quy tắc xoắn ốc tăng dần, bạn có thể nghĩ đến một giải thuật tìm kiếm tận dụng cấu trúc này, mặc dù nó phức tạp hơn nhiều so với tìm kiếm nhị phân trên mảng đã sắp xếp thông thường.

Trọng tâm của việc giải quyết các biến thể này vẫn là việc quản lý biên và hướng di chuyển một cách chính xác.

Bài tập ví dụ:

Ma trận xoáy ốc Fibonacci.

In ra ma trận xoáy ốc cấp N, với các số trong ma trận đều là các số trong dãy Fibonacci.

Input Format

Số nguyên dương N.(1≤N≤9)

Constraints

Output Format

In ra ma trận xoáy ốc cấp N.

Ví dụ:

Dữ liệu vào

Dữ liệu ra

0 1 1 2
89 144 233 3
55 610 377 5
34 21 13 8

Hướng dẫn giải bài "Ma trận xoáy ốc Fibonacci" bằng C++:

Sinh dãy Fibonacci: Tính và lưu trữ N * N số Fibonacci đầu tiên vào một mảng hoặc vector. Bắt đầu từ F0=0, F1=1, F2=1, F3=2, ...
Khởi tạo ma trận: Tạo một ma trận vuông kích thước N x N (ví dụ: vector<vector<long long>> matrix(N, vector<long long>(N));). Nên dùng long long cho các số Fibonacci lớn.
Điền theo xoáy ốc:
- Sử dụng 4 biến để đánh dấu các biên của vùng cần điền: top, bottom, left, right. Ban đầu: top = 0, bottom = N-1, left = 0, right = N-1.
- Sử dụng một chỉ số để theo dõi số Fibonacci tiếp theo cần điền (fib_idx).
- Lặp cho đến khi top > bottom hoặc left > right.
- Trong mỗi vòng lặp, điền các số theo 4 hướng:
  - Từ left đến right trên hàng top. Tăng top.
  - Từ top đến bottom dưới cột right. Giảm right.
  - (Kiểm tra lại điều kiện top <= bottom trước khi điền hướng này) Từ right về left trên hàng bottom. Giảm bottom.
  - (Kiểm tra lại điều kiện left <= right trước khi điền hướng này) Từ bottom về top dưới cột left. Tăng left.
- Sau mỗi lần điền một hướng, tăng fib_idx.
In ma trận: Duyệt qua ma trận đã điền và in ra màn hình theo đúng định dạng (khoảng trắng giữa các số trên cùng một hàng, xuống dòng sau mỗi hàng).

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.