Khóa học C++ từ cơ bản đến nâng cao

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() {
    using namespace std;
    vector<vector<int>> a = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    int r = a.size();
    if (r == 0) return 0;
    int c = a[0].size();
    if (c == 0) return 0;

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

    // Duyet hang dau
    for (int j = 0; j < c; ++j) {
        cout << a[0][j] << " ";
    }

    // Duyet cot cuoi (tru hang dau, neu co nhieu hon 1 hang)
    for (int i = 1; i < r; ++i) {
        cout << a[i][c - 1] << " ";
    }

    // Duyet hang cuoi (tru cot cuoi va cot dau, neu co nhieu hon 1 hang)
    if (r > 1) { 
        for (int j = c - 2; j >= 0; --j) {
            cout << a[r - 1][j] << " ";
        }
    }

    // Duyet cot dau (tru hang dau va hang cuoi, neu co nhieu hon 1 cot)
    if (c > 1) { 
        for (int i = r - 2; i > 0; --i) {
            cout << a[i][0] << " ";
        }
    }

    cout << endl;

    return 0;
}

Output:

Cac phan tu bien cua ma tran:
1 2 3 4 8 12 16 15 14 13 9 5

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 để đảm bảo mỗi phần tử được in một lần:
  • Hàng đầu tiên (a[0][j] cho j từ 0 đến c-1).
  • Cột cuối cùng (a[i][c-1] cho i từ 1 đến r-1) - bắt đầu từ hàng 1 để tránh in lại góc trên bên phải.
  • Hàng cuối cùng (a[r-1][j] cho j từ c-2 xuống 0) - bắt đầu từ cột c-2 và đi ngược lại để tránh in lại góc dưới bên phải và góc dưới bên trái (nếu có). Chỉ duyệt nếu có nhiều hơn 1 hàng.
  • Cột đầu tiên (a[i][0] cho i từ r-2 xuống 1) - bắt đầu từ hàng r-2 và đi ngược lại để tránh in lại góc trên bên trái và góc dưới bên trái. Chỉ duyệt nếu có nhiều hơn 1 cột.
• Các điều kiện if (r > 1) và if (c > 1) giúp xử lý chính xác cho các ma trận nhỏ (1xN, Nx1, 1x1).

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() {
    using namespace std;
    vector<vector<int>> a = {
        { 1,  2,  3,  4},
        { 5,  6,  7,  8},
        { 9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    int n = a.size(); 
    if (n == 0) return 0;

    cout << "Cac phan tu tren duong cheo chinh:\n";
    for (int i = 0; i < n; ++i) {
        cout << a[i][i] << " ";
    }
    cout << endl;

    cout << "Cac phan tu tren duong cheo phu:\n";
    for (int i = 0; i < n; ++i) {
        cout << a[i][n - 1 - i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

Cac phan tu tren duong cheo chinh:
1 6 11 16 
Cac phan tu tren duong cheo phu:
4 7 10 13

Giải thích Code:

• Đối với ma trận vuông kích thước n x n:
  • Đườ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: a[0][0], a[1][1], ..., a[n-1][n-1]. Ta chỉ cần một vòng lặp với biến i từ 0 đến n-1 và truy cập a[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 n - 1: a[0][n-1], a[1][n-2], ..., a[n-1][0]. Ta dùng một vòng lặp với biến i từ 0 đến n-1, chỉ số hàng là i và chỉ số cột là n - 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() {
    using namespace std;
    vector<vector<int>> a = {
        {10, -5, 20},
        { 3,  0, 15},
        {-2, 18,  7}
    };

    int r = a.size();
    if (r == 0) {
        cout << "Ma tran rong." << endl;
        return 0;
    }
    int c = a[0].size();
    if (c == 0) {
         cout << "Ma tran rong." << endl;
        return 0;
    }

    int max_val = numeric_limits<int>::min();
    int min_val = numeric_limits<int>::max();

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (a[i][j] > max_val) {
                max_val = a[i][j];
            }
            if (a[i][j] < min_val) {
                min_val = a[i][j];
            }
        }
    }

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

    return 0;
}

Output:

Phan tu lon nhat: 20
Phan tu nho nhat: -5

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.
• 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 (a[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() {
    using namespace std;
    vector<vector<int>> a = {
        {1, 2, 3},
        {4, 5, 6}
    };

    int r = a.size();
    if (r == 0) return 0;
    int c = a[0].size();
    if (c == 0) return 0;

    vector<vector<int>> b(c, vector<int>(r));

    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            b[j][i] = a[i][j];
        }
    }

    cout << "Ma tran chuyen vi:\n";
    for (int i = 0; i < c; ++i) {
        for (int j = 0; j < r; ++j) {
            cout << b[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

Output:

Ma tran chuyen vi:
1 4 
2 5 
3 6

Giải thích Code:

• Ma trận gốc có r hàng và c cột. Ma trận chuyển vị sẽ có c hàng và r cột.
• Chúng ta tạo một ma trận mới b với kích thước ngược lại: c hàng và r cột.
• Vòng lặp lồng nhau duyệt qua ma trận gốc. Với mỗi phần tử a[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() {
    using namespace std;
    vector<vector<int>> a = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    int r_max = a.size();
    if (r_max == 0) return 0;
    int c_max = a[0].size();
    if (c_max == 0) return 0;

    int r1 = 1, c1 = 1;
    int r2 = 2, c2 = 2;

    if (r1 < 0 || r1 >= r_max || c1 < 0 || c1 >= c_max ||
        r2 < 0 || r2 >= r_max || c2 < 0 || c2 >= c_max ||
        r1 > r2 || c1 > c2) {
        cout << "Toa do vung con khong hop le." << endl;
        return 0;
    }

    long long tong = 0;

    for (int i = r1; i <= r2; ++i) {
        for (int j = c1; j <= c2; ++j) {
            tong += a[i][j];
        }
    }

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

    return 0;
}

Output:

Tong cac phan tu trong vung con (1,1) den (2,2) la: 34

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 tong. Sử dụng long long cho tong 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ố.