Bài 27.5: Bài tập thực hành mảng 2 chiều nâng cao trong C++

Chào mừng trở lại với chuỗi bài học C++ của chúng ta! Sau khi đã làm quen với những kiến thức cơ bản về mảng 2 chiều (hay còn gọi là ma trận), cách khai báo, khởi tạo và duyệt qua các phần tử, hôm nay chúng ta sẽ cùng lặn sâu hơn vào thế giới của chúng thông qua các bài tập mang tính thử thách hơn. Đây là lúc để củng cố kiến thức và phát triển kỹ năng xử lý các cấu trúc dữ liệu phức tạp hơn.

Mảng 2 chiều là một công cụ mạnh mẽ để biểu diễn các dữ liệu có cấu trúc dạng lưới, bảng, hoặc ma trận. Việc thành thạo cách thao tác với mảng 2 chiều không chỉ giúp bạn giải quyết các bài toán lập trình thi đấu mà còn rất hữu ích trong nhiều ứng dụng thực tế như xử lý ảnh đơn giản, trò chơi (như caro, mìn), hay các bài toán quy hoạch động trên lưới.

Các bài tập nâng cao thường yêu cầu bạn suy nghĩ sáng tạo hơn về cách duyệt mảng, cách lưu trữ thông tin hoặc cách biến đổi cấu trúc dữ liệu ban đầu. Chúng ta sẽ cùng đi qua một vài ví dụ điển hình để bạn có cái nhìn rõ hơn.

Tại sao cần luyện tập mảng 2 chiều nâng cao?

Bạn có thể tự hỏi: "Tôi đã biết cách duyệt mảng từ đầu đến cuối rồi, còn gì nữa đâu?". À không, mảng 2 chiều còn rất nhiều điều thú vị đấy! Các bài tập nâng cao giúp bạn:

  1. Hiểu sâu hơn về chỉ mục (index): Các bài toán thường yêu cầu bạn tính toán chỉ mục một cách linh hoạt, không chỉ đơn thuần là [i][j].
  2. Phát triển tư duy giải thuật: Nhiều bài toán trên mảng 2 chiều có thể được giải quyết bằng các thuật toán kinh điển hoặc các biến thể của chúng (ví dụ: tìm đường đi, đếm thành phần liên thông).
  3. Chuẩn bị cho cấu trúc dữ liệu phức tạp hơn: Mảng 2 chiều là bước đệm quan trọng để làm quen với các cấu trúc dữ liệu đồ họa hoặc lưới phức tạp hơn sau này.
  4. Cải thiện kỹ năng debug: Khi code phức tạp hơn, việc tìm lỗi sai trong vòng lặp và chỉ mục là một kỹ năng thiết yếu.

Không nói nhiều nữa, chúng ta hãy bắt tay vào thực hành ngay thôi!

Các dạng bài tập thực hành nâng cao

Dưới đây là một số dạng bài tập phổ biến khi làm việc với mảng 2 chiều ở mức độ nâng cao hơn một chút so với cơ bản.

Bài tập 1: Duyệt các phần tử biên (Border Traversal)

Thay vì duyệt toàn bộ mảng, bài tập này yêu cầu bạn chỉ xử lý các phần tử nằm ở biên của ma trận.

Yêu cầu: In ra tất cả các phần tử nằm trên hàng đầu tiên, hàng cuối cùng, cột đầu tiên và cột cuối cùng của một ma trận cho trước. Chú ý in mỗi phần tử một lần.

Ví dụ Code:

#include <iostream>
#include <vector>

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    int rows = matrix.size();
    if (rows == 0) return 0; // Xử lý trường hợp mảng rỗng
    int cols = matrix[0].size();
    if (cols == 0) return 0; // Xử lý trường hợp hàng rỗng

    cout << "Cac phan tu bien cua ma tran:\n";

    // Duyệt hàng đầu tiên
    for (int j = 0; j < cols; ++j) {
        cout << matrix[0][j] << " ";
    }

    // Duyệt hàng cuối cùng (tránh in lại góc phải dưới nếu chỉ có 1 hàng)
    if (rows > 1) {
        for (int j = 0; j < cols; ++j) {
            cout << matrix[rows - 1][j] << " ";
        }
    }

    // Duyệt cột đầu tiên (tránh in lại góc trên/dưới bên trái)
    if (cols > 1) {
        for (int i = 1; i < rows - 1; ++i) { // Bắt đầu từ hàng 1, kết thúc ở hàng rows-2
            cout << matrix[i][0] << " ";
        }
    }

    // Duyệt cột cuối cùng (tránh in lại góc trên/dưới bên phải)
     if (cols > 1 && rows > 1) { // Chỉ duyệt cột cuối nếu có ít nhất 2 cột và 2 hàng
        for (int i = 1; i < rows - 1; ++i) { // Bắt đầu từ hàng 1, kết thúc ở hàng rows-2
            cout << matrix[i][cols - 1] << " ";
        }
    }


    cout << endl;

    return 0;
}

Giải thích Code:

  • Chúng ta sử dụng vector<vector<int>> để biểu diễn ma trận, đây là cách phổ biến và linh hoạt trong C++.
  • Đoạn code duyệt qua từng phần của biên:
    • Hàng đầu tiên (matrix[0][j] cho j từ 0 đến cols-1).
    • Hàng cuối cùng (matrix[rows-1][j] cho j từ 0 đến cols-1).
    • Cột đầu tiên (matrix[i][0] cho i từ 1 đến rows-2) - ta bắt đầu từ i=1 và kết thúc ở rows-2 để tránh in lại các phần tử ở góc (đã được in khi duyệt hàng đầu và hàng cuối).
    • Cột cuối cùng (matrix[i][cols-1] cho i từ 1 đến rows-2) - tương tự, tránh in lại các phần tử góc.
  • Các điều kiện if (rows > 1), if (cols > 1), if (cols > 1 && rows > 1) giúp xử lý chính xác cho các ma trận nhỏ (1xN, Nx1, 1x1) để tránh truy cập ra ngoài phạm vi hoặc in trùng lặp.
Bài tập 2: Duyệt các phần tử trên đường chéo (Diagonal Traversal)

Bài tập này tập trung vào các phần tử nằm trên hai đường chéo chính của ma trận (đường chéo chính và đường chéo phụ).

Yêu cầu: Cho một ma trận vuông, in ra các phần tử nằm trên đường chéo chính và các phần tử nằm trên đường chéo phụ.

Ví dụ Code:

#include <iostream>
#include <vector>

int main() {
    vector<vector<int>> matrix = {
        { 1,  2,  3,  4},
        { 5,  6,  7,  8},
        { 9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    int size = matrix.size(); // Giả sử ma trận vuông

    if (size == 0) return 0; // Xử lý trường hợp mảng rỗng

    cout << "Cac phan tu tren duong cheo chinh:\n";
    for (int i = 0; i < size; ++i) {
        cout << matrix[i][i] << " "; // Chi so hang va cot bang nhau
    }
    cout << endl;

    cout << "Cac phan tu tren duong cheo phu:\n";
    for (int i = 0; i < size; ++i) {
        // Chi so hang tang, chi so cot giam tu cuoi ve dau
        cout << matrix[i][size - 1 - i] << " ";
    }
    cout << endl;

    return 0;
}

Giải thích Code:

  • Đối với ma trận vuông kích thước size x size:
    • Đường chéo chính bao gồm các phần tử có chỉ số hàng và chỉ số cột bằng nhau: matrix[0][0], matrix[1][1], ..., matrix[size-1][size-1]. Ta chỉ cần một vòng lặp với biến i từ 0 đến size-1 và truy cập matrix[i][i].
    • Đường chéo phụ bao gồm các phần tử có tổng chỉ số hàng và chỉ số cột bằng size - 1: matrix[0][size-1], matrix[1][size-2], ..., matrix[size-1][0]. Ta dùng một vòng lặp với biến i từ 0 đến size-1, chỉ số hàng là i và chỉ số cột là size - 1 - i.
Bài tập 3: Tìm phần tử lớn nhất/nhỏ nhất

Đây là một bài tập cơ bản nhưng khi áp dụng cho mảng 2 chiều, nó giúp bạn củng cố cách duyệt và so sánh các phần tử.

Yêu cầu: Tìm và in ra phần tử có giá trị lớn nhất và nhỏ nhất trong ma trận.

Ví dụ Code:

#include <iostream>
#include <vector>
#include <limits> // For numeric_limits

int main() {
    vector<vector<int>> matrix = {
        {10, -5, 20},
        { 3,  0, 15},
        {-2, 18,  7}
    };

    int rows = matrix.size();
    if (rows == 0) {
        cout << "Ma tran rong." << endl;
        return 0;
    }
    int cols = matrix[0].size();
    if (cols == 0) {
         cout << "Ma tran rong." << endl;
        return 0;
    }

    int max_val = numeric_limits<int>::min(); // Khởi tạo max bằng giá trị rất nhỏ
    int min_val = numeric_limits<int>::max(); // Khởi tạo min bằng giá trị rất lớn

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (matrix[i][j] > max_val) {
                max_val = matrix[i][j]; // Cap nhat gia tri lon nhat
            }
            if (matrix[i][j] < min_val) {
                min_val = matrix[i][j]; // Cap nhat gia tri nho nhat
            }
        }
    }

    cout << "Phan tu lon nhat: " << max_val << endl;
    cout << "Phan tu nho nhat: " << min_val << endl;

    return 0;
}

Giải thích Code:

  • Chúng ta khởi tạo max_val bằng giá trị nhỏ nhất có thể của kiểu int (numeric_limits<int>::min()) và min_val bằng giá trị lớn nhất có thể (numeric_limits<int>::max()). Cách này an toàn hơn việc khởi tạo bằng phần tử đầu tiên của mảng, đặc biệt khi mảng có thể có các giá trị âm hoặc rất lớn/nhỏ.
  • Sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các phần tử trong ma trận.
  • Trong mỗi lần lặp, ta so sánh phần tử hiện tại (matrix[i][j]) với max_val và min_val đang có. Nếu lớn hơn max_val thì cập nhật max_val; nếu nhỏ hơn min_val thì cập nhật min_val.
  • Sau khi duyệt hết mảng, max_val và min_val sẽ chứa giá trị lớn nhất và nhỏ nhất.
Bài tập 4: Chuyển vị ma trận (Matrix Transpose)

Chuyển vị ma trận là bài toán kinh điển, nơi hàng trở thành cột và cột trở thành hàng.

Yêu cầu: Cho một ma trận gốc kích thước rows x cols, tạo ra một ma trận mới là ma trận chuyển vị của nó với kích thước cols x rows.

Ví dụ Code:

#include <iostream>
#include <vector>

int main() {
    vector<vector<int>> original_matrix = {
        {1, 2, 3},
        {4, 5, 6}
    };

    int rows = original_matrix.size();
    if (rows == 0) return 0;
    int cols = original_matrix[0].size();
    if (cols == 0) return 0;

    // Ma tran chuyen vi se co kich thuoc cols x rows
    vector<vector<int>> transposed_matrix(cols, vector<int>(rows));

    // Thuc hien chuyen vi
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            transposed_matrix[j][i] = original_matrix[i][j]; // Hoan doi chi so
        }
    }

    cout << "Ma tran chuyen vi:\n";
    for (int i = 0; i < cols; ++i) { // Duyet tren ma tran moi
        for (int j = 0; j < rows; ++j) {
            cout << transposed_matrix[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Giải thích Code:

  • Ma trận gốc có rows hàng và cols cột. Ma trận chuyển vị sẽ có cols hàng và rows cột.
  • Chúng ta tạo một ma trận mới transposed_matrix với kích thước ngược lại: cols hàng và rows cột. Cú pháp vector<vector<int>>(cols, vector<int>(rows)) tạo ra một vector gồm cols phần tử, mỗi phần tử là một vector con có rows phần tử int (mặc định khởi tạo là 0).
  • Vòng lặp lồng nhau duyệt qua ma trận gốc. Với mỗi phần tử original_matrix[i][j] (ở hàng i, cột j của ma trận gốc), nó sẽ được đặt vào vị trí [j][i] (hàng j, cột i) trong ma trận chuyển vị.
  • Sau khi điền đầy đủ các phần tử, chúng ta in ma trận chuyển vị, nhớ rằng số hàng và cột đã thay đổi.
Bài tập 5: Tính tổng các phần tử trong một vùng con

Bài tập này yêu cầu bạn trích xuất và xử lý dữ liệu từ một phần cụ thể của ma trận.

Yêu cầu: Cho một ma trận và tọa độ của hai góc đối diện của một hình chữ nhật con (ví dụ: góc trên bên trái (r1, c1) và góc dưới bên phải (r2, c2)), tính tổng tất cả các phần tử nằm trong vùng hình chữ nhật đó.

Ví dụ Code:

#include <iostream>
#include <vector>

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    int rows = matrix.size();
    if (rows == 0) return 0;
    int cols = matrix[0].size();
    if (cols == 0) return 0;

    // Toa do vung con: goc tren trai (r1, c1), goc duoi phai (r2, c2)
    int r1 = 1, c1 = 1;
    int r2 = 2, c2 = 2; // Vung con: matrix[1][1] den matrix[2][2] (cac phan tu 6, 7, 10, 11)

    // Kiem tra toa do hop le
    if (r1 < 0 || r1 >= rows || c1 < 0 || c1 >= cols ||
        r2 < 0 || r2 >= rows || c2 < 0 || c2 >= cols ||
        r1 > r2 || c1 > c2) {
        cout << "Toa do vung con khong hop le." << endl;
        return 0;
    }

    long long sum = 0; // Su dung long long de tranh tran so neu tong lon

    // Duyet cac phan tu trong vung con
    for (int i = r1; i <= r2; ++i) {
        for (int j = c1; j <= c2; ++j) {
            sum += matrix[i][j];
        }
    }

    cout << "Tong cac phan tu trong vung con (" << r1 << "," << c1 << ") den (" << r2 << "," << c2 << ") la: " << sum << endl;

    return 0;
}

Giải thích Code:

  • Chúng ta định nghĩa tọa độ góc trên bên trái (r1, c1) và góc dưới bên phải (r2, c2) của vùng con.
  • Kiểm tra tính hợp lệ của các tọa độ là bước quan trọng để tránh lỗi truy cập mảng ngoài phạm vi và đảm bảo vùng con hợp lý (góc trên trái phải nằm trên/bên trái góc dưới phải).
  • Sử dụng hai vòng lặp lồng nhau, nhưng lần này các chỉ số bắt đầu từ r1 đến r2 cho hàng và c1 đến c2 cho cột, thay vì từ 0 đến kích thước đầy đủ của ma trận.
  • Cộng dồn giá trị của các phần tử nằm trong phạm vi chỉ mục này vào biến sum. Sử dụng long long cho sum là một cách phòng ngừa tốt nếu ma trận chứa các số lớn và vùng con rộng, tránh bị tràn số.

Comments

There are no comments at the moment.