Bài 25.2: Duyệt mảng 2 chiều trong C++

Chào mừng trở lại với series học lập trình C++ cùng FullhouseDev! Sau khi đã nắm vững khái niệm mảng 1 chiều và cách duyệt chúng, hôm nay chúng ta sẽ nâng cấp độ khó một chút và tìm hiểu về mảng 2 chiều.

Mảng 2 chiều (hay còn gọi là ma trận trong toán học) là một cấu trúc dữ liệu cực kỳ hữu ích để biểu diễn dữ liệu dưới dạng lưới, bảng, hoặc các đối tượng có chiều ngang và chiều dọc, ví dụ như hình ảnh (pixel), bản đồ (ô), hay bảng tính. Và kỹ năng quan trọng nhất khi làm việc với mảng 2 chiều chính là duyệt (iteration) - truy cập và xử lý từng phần tử trong mảng.

Mảng 2 chiều là gì?

Hãy tưởng tượng mảng 2 chiều như một tấm lưới hoặc một bảng tính Excel. Nó có các hàng (rows) và các cột (columns). Mỗi phần tử được xác định bằng chỉ số hàng và chỉ số cột của nó.

Trong C++, bạn có thể khai báo mảng 2 chiều theo hai cách phổ biến:

Mảng kiểu C cổ điển (fixed size):
```
int matrix[3][4]; // Mang 3 hang, 4 cot
```
Kích thước phải được xác định tại thời điểm biên dịch.
Sử dụng vector<vector<T>>: Linh hoạt hơn, kích thước có thể thay đổi động.
```
#include <vector>
vector<vector<int>> dynamic_matrix(3, vector<int>(4)); // Mang 3 hang, 4 cot
```
Cách này thường được ưa chuộng hơn trong C++ hiện đại vì tính linh hoạt.

Kỹ thuật Duyệt Mảng 2 Chiều

Để duyệt qua tất cả các phần tử trong mảng 2 chiều, chúng ta cần một cách để truy cập từng vị trí (hàng, cột). Phương pháp phổ biến và cơ bản nhất chính là sử dụng vòng lặp for lồng nhau.

Phương pháp 1: Vòng Lặp `for` Lồng Nhau (Index-based)

Đây là cách tiếp cận trực tiếp nhất. Chúng ta sẽ sử dụng:

Một vòng lặp for bên ngoài để duyệt qua các hàng.
Một vòng lặp for bên trong để duyệt qua các cột cho mỗi hàng hiện tại.

Cấu trúc chung sẽ trông như thế này:

for (int i = 0; i < so_hang; ++i) { // Vong lap ngoai: Duyet qua cac hang (chi so i)
    for (int j = 0; j < so_cot; ++j) { // Vong lap trong: Duyet qua cac cot (chi so j) trong hang i
        // Truy cap phan tu tai matrix[i][j] va xu ly
    }
}

Trong đó, i là chỉ số hàng (thường bắt đầu từ 0) và j là chỉ số cột (cũng bắt đầu từ 0). matrix[i][j] sẽ cho phép bạn truy cập phần tử tại hàng i và cột j.

Ví dụ 1: Duyệt và in Mảng Cổ Điển

Hãy xem xét một ví dụ với mảng cố định kích thước:

#include <iostream>

int main() {
    // Khai bao va khoi tao mang 2 chieu co dinh
    int matrix[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };

    cout << "Duyet mang 2 chieu (fixed size) bang nested for loops:\n";

    // Duyet qua cac hang
    for (int i = 0; i < 3; ++i) {
        // Duyet qua cac cot trong hang hien tai
        for (int j = 0; j < 4; ++j) {
            // In gia tri phan tu tai vi tri [i][j]
            cout << matrix[i][j] << " ";
        }
        // Xuong dong sau khi ket thuc mot hang de in dung dinh dang ma tran
        cout << endl;
    }

    return 0;
}

Giải thích:

Vòng lặp ngoài for (int i = 0; i < 3; ++i) chạy từ i = 0 đến i = 2, đại diện cho 3 hàng của ma trận.
Với mỗi giá trị của i, vòng lặp trong for (int j = 0; j < 4; ++j) chạy từ j = 0 đến j = 3, đại diện cho 4 cột trong hàng i đó.
cout << matrix[i][j] << " "; in ra giá trị của phần tử tại hàng i, cột j, theo sau là một khoảng trắng.
cout << endl; được gọi sau khi vòng lặp trong (duyệt cột) kết thúc, đảm bảo mỗi hàng của ma trận được in trên một dòng mới.

Ví dụ 2: Duyệt và in với `vector<vector<int>>`

Với vector<vector<int>>, chúng ta có thể lấy kích thước hàng và cột một cách linh hoạt bằng phương thức .size().

#include <iostream>
#include <vector>

int main() {
    // Khai bao va khoi tao vector cua cac vector
    vector<vector<int>> dynamic_matrix = {
        {10, 20, 30},
        {40, 50, 60},
        {70, 80, 90},
        {100, 110, 120}
    };

    // Lay so luong hang
    int num_rows = dynamic_matrix.size();
    // Lay so luong cot tu hang dau tien (gia dinh cac hang co cung kich thuoc)
    // Can luu y: neu cac hang co kich thuoc khac nhau, ban can lay dynamic_matrix[i].size() trong vong lap inner
    int num_cols = dynamic_matrix[0].size();

    cout << "Duyet mang 2 chieu (vector<vector>) bang nested for loops:\n";

    // Duyet qua cac hang
    for (int i = 0; i < num_rows; ++i) {
        // Duyet qua cac cot trong hang hien tai
        for (int j = 0; j < num_cols; ++j) {
            // In gia tri phan tu tai vi tri [i][j]
            cout << dynamic_matrix[i][j] << " ";
        }
        // Xuong dong sau moi hang
        cout << endl;
    }

    return 0;
}

Giải thích:

Tương tự như ví dụ 1, chúng ta dùng hai vòng lặp for lồng nhau.
Điểm khác biệt là số lượng hàng (num_rows) được lấy bằng dynamic_matrix.size(), và số lượng cột (num_cols) được lấy bằng dynamic_matrix[0].size(). Điều này làm cho code linh hoạt hơn với các ma trận có kích thước khác nhau mà không cần sửa lại chỉ số cố định trong vòng lặp.
Việc truy cập phần tử vẫn là dynamic_matrix[i][j].

Phương pháp 2: Vòng Lặp `range-based for` Lồng Nhau (chỉ với `vector<vector<T>>`)

Với vector<vector<T>>, bạn có thể sử dụng cú pháp range-based for của C++11 trở lên để duyệt mảng. Cách này trừu tượng hơn chỉ số i, j, nhưng có thể gọn gàng hơn khi bạn chỉ cần truy cập giá trị của phần tử mà không cần biết vị trí chính xác của nó.

Vòng lặp range-based for bên ngoài sẽ duyệt qua từng vector (hàng) trong vector<vector<T>> lớn.
Vòng lặp range-based for bên trong sẽ duyệt qua từng phần tử trong vector (hàng) hiện tại.

for (const auto& hang : mang_vector_2d) { // Vong lap ngoai: Duyet qua tung hang (moi hang la mot vector)
    for (int phan_tu : hang) { // Vong lap trong: Duyet qua tung phan tu trong hang hien tai
        // Xu ly phan_tu
    }
}

Ví dụ 3: Duyệt và in với Range-Based For

#include <iostream>
#include <vector>

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    cout << "Duyet mang 2 chieu (vector<vector>) bang nested range-based for loops:\n";

    // Vong lap ngoai: Duyet qua tung vector con (tung hang)
    for (const auto& row : matrix) {
        // Vong lap trong: Duyet qua tung phan tu trong vector con hien tai (hang hien tai)
        for (int element : row) {
            cout << element << " ";
        }
        // Xuong dong sau moi hang
        cout << endl;
    }

    return 0;
}

Giải thích:

Vòng lặp ngoài for (const auto& row : matrix): row là một tham chiếu (để tránh copy) đến từng vector<int> trong matrix. const auto& là một cách viết tắt thuận tiện.
Vòng lặp trong for (int element : row): element là từng phần tử kiểu int trong vector<int> hiện tại (row).
Cách này không cho bạn trực tiếp chỉ số i và j của phần tử. Nếu bạn cần chỉ số, bạn phải sử dụng vòng lặp index-based hoặc tự duy trì biến đếm chỉ số. Tuy nhiên, khi chỉ cần đọc hoặc xử lý giá trị, cách này rất gọn gàng.

Các Ví Dụ Thực Tế Hơn Khi Duyệt Mảng 2 Chiều

Vòng lặp lồng nhau không chỉ để in mảng. Chúng cho phép bạn thực hiện mọi thao tác với từng phần tử. Dưới đây là một vài ví dụ khác:

Ví dụ 4: Tính Tổng Tất Cả Các Phần Tử

#include <iostream>
#include <vector>

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    long long total_sum = 0; // Su dung long long de tranh tran so neu cac phan tu lon

    cout << "\nTinh tong cac phan tu trong mang:\n";

    // Duyet qua tat ca cac phan tu va cong vao bien total_sum
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = 0; j < matrix[i].size(); ++j) {
            total_sum += matrix[i][j];
        }
    }

    cout << "Tong tat ca cac phan tu la: " << total_sum << endl;

    return 0;
}

Giải thích:

Chúng ta khai báo một biến total_sum và khởi tạo nó bằng 0.
Sử dụng vòng lặp for lồng nhau (index-based) để duyệt qua từng phần tử matrix[i][j].
Trong vòng lặp trong, chúng ta cộng giá trị của phần tử hiện tại vào total_sum.
Kết quả cuối cùng là tổng của tất cả các phần tử.

Ví dụ 5: Tìm Kiếm Một Phần Tử Cụ Thể

#include <iostream>
#include <vector>

int main() {
    vector<vector<int>> matrix = {
        {10, 20, 30},
        {40, 50, 60},
        {70, 80, 90}
    };

    int target = 50;
    bool found = false;
    int found_row = -1, found_col = -1;

    cout << "\nTim kiem phan tu " << target << " trong mang:\n";

    // Duyet qua tat ca cac phan tu de tim target
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = 0; j < matrix[i].size(); ++j) {
            if (matrix[i][j] == target) {
                found = true;       // Danh dau da tim thay
                found_row = i;      // Luu lai chi so hang
                found_col = j;      // Luu lai chi so cot
                // Neu chi can vi tri dau tien, co the them 'break;' tai day
                // break; // Thoat vong lap inner
            }
        }
        // Neu chi can vi tri dau tien, co the them 'if (found) break;' tai day
        // if (found) break; // Thoat vong lap outer
    }

    if (found) {
        cout << "Tim thay phan tu " << target << " tai vi tri [" << found_row << "][" << found_col << "]" << endl;
    } else {
        cout << "Khong tim thay phan tu " << target << " trong mang." << endl;
    }

    return 0;
}

Giải thích:

Chúng ta sử dụng vòng lặp lồng nhau để kiểm tra từng phần tử.
Nếu matrix[i][j] bằng với giá trị target, chúng ta đánh dấu found = true và lưu lại chỉ số i và j.
Biến found được sử dụng sau vòng lặp để thông báo kết quả.
Việc sử dụng break (đã comment trong code) có thể giúp thoát vòng lặp sớm ngay sau khi tìm thấy phần tử đầu tiên, làm cho chương trình hiệu quả hơn nếu mảng lớn.

Ví dụ 6: Khởi Tạo Mảng với Giá Trị Dựa Trên Vị Trí

Bạn cũng có thể dùng vòng lặp lồng nhau để gán giá trị cho mảng, ví dụ như điền số từ 0 đến nm-1, hoặc giá trị dựa trên công thức `i10 + j`.

#include <iostream>
#include <vector>

int main() {
    int num_rows = 5;
    int num_cols = 6;

    // Khai bao vector cua cac vector voi kich thuoc truoc
    vector<vector<int>> matrix(num_rows, vector<int>(num_cols));

    cout << "\nKhoi tao mang voi gia tri dua tren vi tri (i, j) va in ra:\n";

    // Duyet qua mang de gan gia tri
    for (int i = 0; i < num_rows; ++i) {
        for (int j = 0; j < num_cols; ++j) {
            // Gan gia tri = cong thuc dua tren i va j
            matrix[i][j] = i * 10 + j;
        }
    }

    // Duyet lai mang de in ket qua (de kiem tra)
    for (int i = 0; i < num_rows; ++i) {
        for (int j = 0; j < num_cols; ++j) {
            cout << matrix[i][j] << "\t"; // Su dung tab de can le
        }
        cout << endl;
    }

    return 0;
}

Giải thích:

Đầu tiên, chúng ta khai báo vector<vector<int>> matrix với kích thước num_rows x num_cols.
Vòng lặp lồng nhau được sử dụng để truy cập từng vị trí [i][j] và gán giá trị i * 10 + j vào đó.
Sau đó, chúng ta sử dụng một cặp vòng lặp lồng nhau khác để in ra ma trận đã được gán giá trị để kiểm tra.

Khi Nào Sử Dụng Cách Nào?

Sử dụng vòng lặp for lồng nhau với chỉ số (int i, int j) khi bạn cần truy cập phần tử dựa trên vị trí chính xác của nó (hàng i, cột j) hoặc khi bạn làm việc với mảng C cố định kích thước. Đây là phương pháp linh hoạt nhất và mạnh mẽ nhất cho mảng 2 chiều.
Sử dụng vòng lặp range-based for lồng nhau khi bạn làm việc với vector<vector<T>> và chỉ cần truy cập giá trị của từng phần tử mà không quan tâm đến chỉ số i, j của nó. Cách này giúp code gọn gàng và dễ đọc hơn trong trường hợp đơn giản.

Những Điểm Cần Lưu Ý

Luôn nhớ kích thước của mảng (số hàng và số cột) khi sử dụng vòng lặp index-based để tránh truy cập ngoài giới hạn mảng (out-of-bounds access), dẫn đến lỗi runtime nghiêm trọng. Với vector, luôn sử dụng .size() để lấy kích thước động.
Thứ tự duyệt thông thường là duyệt hết các cột của một hàng rồi mới sang hàng tiếp theo (row-major order). Thứ tự này tương ứng với cách mảng 2 chiều thường được lưu trữ trong bộ nhớ và thường là hiệu quả nhất.

Bài tập ví dụ: C++ Bài 11.A2: Số lớn nhất trong ma trận

Viết chương trình nhập vào ma trận số nguyên gồm \(n\) dòng \(n\) cột. Tìm và thông báo số lớn nhất trên mỗi hàng..

INPUT FORMAT

Dòng đầu là hai số nguyên dương \(n\) \((1 \leq n \leq 1000)\)

Các dòng tiếp theo là ma trận số nguyên \(A\).

OUTPUT FORMAT

In ra \(n\) dòng, mỗi dòng là số lớn nhất trên dòng đó.

Ví dụ:

Input

Output

4
8
8

Giải thích ví dụ mẫu

Tìm giá trị lớn nhất trên mỗi hàng của ma trận và in ra kết quả.

<br>

Ý tưởng chính:

Bài toán yêu cầu xử lý từng hàng của ma trận một cách độc lập để tìm giá trị lớn nhất. Vì vậy, chúng ta sẽ lặp qua từng hàng của ma trận, và với mỗi hàng, chúng ta sẽ tìm giá trị lớn nhất trong hàng đó rồi in ra.

Các bước thực hiện:

Đọc kích thước ma trận:
- Đầu tiên, bạn cần đọc số nguyên n từ đầu vào để biết kích thước của ma trận (n dòng, n cột).
Xử lý từng hàng:
- Sử dụng một vòng lặp để duyệt qua từng dòng của ma trận, từ dòng 0 đến dòng n-1.
- Bên trong vòng lặp này, bạn sẽ xử lý cho một dòng hiện tại.
Đọc và tìm giá trị lớn nhất trên một hàng:
- Đối với dòng hiện tại, bạn cần đọc n số nguyên là các phần tử của dòng đó.
- Có nhiều cách để tìm giá trị lớn nhất trên hàng này:
  - Cách thủ công: Khởi tạo một biến max_val với giá trị của phần tử đầu tiên trên hàng. Sau đó, duyệt qua các phần tử còn lại trên hàng, so sánh từng phần tử với max_val. Nếu phần tử hiện tại lớn hơn max_val, cập nhật max_val.
  - Sử dụng max_element: Đây là cách C++ hiện đại sử dụng thư viện chuẩn và thường ngắn gọn hơn. Bạn có thể đọc các phần tử của dòng hiện tại vào một container như vector<int>. Sau đó, sử dụng hàm max_element (có trong header <algorithm>) để tìm con trỏ (hoặc iterator) tới phần tử lớn nhất trong vector đó. Hàm này nhận vào hai iterator chỉ phạm vi cần tìm (ví dụ: vector.begin() và vector.end()). Giá trị lớn nhất chính là giá trị mà iterator trả về trỏ tới (dùng toán tử * để lấy giá trị).
In kết quả:
- Sau khi đã tìm được giá trị lớn nhất (max_val) của dòng hiện tại, bạn cần in giá trị này ra màn hình.
- Mỗi giá trị lớn nhất của mỗi dòng nên được in trên một dòng riêng, theo đúng định dạng đầu ra yêu cầu.
Bao gồm các thư viện cần thiết:
- Bạn sẽ cần <iostream> cho việc nhập/xuất dữ liệu.
- Nếu sử dụng vector, bạn cần <vector>.
- Nếu sử dụng max_element, bạn cần <algorithm>.

Gợi ý về cấu trúc code (không phải code hoàn chỉnh):

#include <iostream>
#include <vector> // Nếu dùng vector
#include <algorithm> // Nếu dùng max_element
#include <limits> // Có thể dùng để khởi tạo giá trị lớn nhất ban đầu (tùy cách làm)

int main() {
    // Tắt đồng bộ hóa với C stdout để nhập xuất nhanh hơn (tùy chọn, hữu ích với n lớn)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    // Đọc n

    // Vòng lặp xử lý từng dòng (i từ 0 đến n-1)
    for (int i = 0; i < n; ++i) {
        // Cách 1: Đọc từng phần tử của dòng và tìm max ngay
        // Khởi tạo max_val cho dòng hiện tại (ví dụ, bằng phần tử đầu tiên hoặc giá trị rất nhỏ)
        // Vòng lặp đọc n phần tử của dòng (j từ 0 đến n-1)
            // Đọc phần tử hiện tại
            // So sánh và cập nhật max_val nếu cần

        // Cách 2: Đọc toàn bộ dòng vào vector rồi dùng max_element
        // Tạo một vector cho dòng hiện tại
        // Vòng lặp đọc n phần tử vào vector
        // Tìm max_val trong vector dùng max_element
        // Lấy giá trị từ iterator trả về

        // In max_val của dòng hiện tại, theo sau là xuống dòng
    }

    return 0;
}

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

Comments

There are no comments at the moment.