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

Bài 25.4: Kỹ thuật loang trên mảng 2 chiều trong C++

Chào mừng bạn quay trở lại với series về C++ của FullhouseDev! Hôm nay, chúng ta sẽ cùng nhau "lặn sâu" vào một kỹ thuật quen зовсім quen thuộc trong nhiều lĩnh vực, từ chỉnh sửa ảnh đơn giản đến các bài toán phức tạp trên đồ thị: Kỹ thuật loang, hay còn gọi là Flood Fill.

Bạn đã bao giờ sử dụng công cụ "thùng sơn" trong các phần mềm đồ họa để tô màu một vùng liền mạch chưa? Đó chính là một ứng dụng trực quan của kỹ thuật loang đấy! Về cơ bản, kỹ thuật này giúp chúng ta xác định và thao tác (ví dụ: thay đổi màu, đếm số lượng) với một vùng liền kề các phần tử có cùng một thuộc tính (giá trị) trong một cấu trúc dữ liệu dạng lưới hoặc mảng 2 chiều.

Hãy tưởng tượng bạn có một tấm bản đồ số được biểu diễn bằng một mảng 2 chiều, nơi mỗi ô chứa một giá trị đại diện cho loại địa hình (ví dụ: 0 cho nước, 1 cho đất liền). Kỹ thuật loang có thể giúp bạn:

• Tô màu toàn bộ một hồ nước sau khi click vào một điểm bất kỳ trong hồ đó.
• Đếm diện tích của một "hòn đảo" (vùng đất liền liên tục).
• Tìm tất cả các ô trống liên thông trong một mê cung để xem có đường đi không.

Sức mạnh của kỹ thuật này nằm ở khả năng lan tỏa từ một điểm gốc ra các điểm lân cận, nhưng chỉ khi các điểm lân cận đó đáp ứng một điều kiện nhất định (thường là có cùng giá trị với điểm gốc hoặc giá trị mà ta muốn thay đổi).

Kỹ thuật Loang Hoạt Động Như Thế Nào?

Ý tưởng cốt lõi rất đơn giản:

1. Bạn bắt đầu từ một điểm $(r, c)$ trên lưới.
2. Kiểm tra xem điểm này có hợp lệ để "loang" không (ví dụ: nằm trong biên của lưới, có giá trị mong muốn).
3. Nếu hợp lệ, bạn xử lý điểm đó (ví dụ: thay đổi giá trị của nó để đánh dấu là đã thăm hoặc thay đổi màu).
4. Sau đó, bạn loang sang các điểm lân cận của nó (trên, dưới, trái, phải - hoặc cả 8 hướng tùy bài toán) và lặp lại quá trình này cho đến khi không còn điểm lân cận hợp lệ nào để loang nữa.

Quá trình "loang sang các điểm lân cận" chính là phần quan trọng nhất và có thể được triển khai theo hai cách phổ biến:

1. Sử dụng Đệ quy (Depth-First Search - DFS)

DFS về bản chất là đi sâu vào một nhánh trước khi quay lại và khám phá các nhánh khác. Với kỹ thuật loang, khi bạn loang từ $(r, c)$, bạn ngay lập tức gọi đệ quy để loang từ một trong các ô lân cận hợp lệ của nó.

Cấu trúc cơ bản của một hàm loang DFS:

void flood_fill_dfs(int r, int c, int old_value, int new_value, vector<vector<int>>& grid) {
    // 1. Kiểm tra điều kiện dừng/biên
    //    - R, C nằm ngoài biên? -> Dừng
    //    - Ô hiện tại có giá trị khác old_value? -> Dừng
    //    - Ô hiện tại đã có giá trị new_value (đã thăm)? -> Dừng (nếu new_value khác old_value)

    // 2. Xử lý ô hiện tại
    //    - Đặt giá trị của ô hiện tại thành new_value

    // 3. Gọi đệ quy loang sang các ô lân cận (4 hướng hoặc 8 hướng)
    //    - flood_fill_dfs(r-1, c, old_value, new_value, grid) // Lên
    //    - flood_fill_dfs(r+1, c, old_value, new_value, grid) // Xuống
    //    - flood_fill_dfs(r, c-1, old_value, new_value, grid) // Trái
    //    - flood_fill_dfs(r, c+1, old_value, new_value, grid) // Phải
}

Để thuận tiện cho việc duyệt các ô lân cận, chúng ta thường sử dụng hai mảng dr và dc lưu trữ sự thay đổi về chỉ số hàng và cột.

Ví dụ minh họa Flood Fill bằng DFS (4 hướng):

Giả sử chúng ta có một mảng biểu diễn vùng nước (0) và đất (1), muốn thay đổi tất cả vùng nước liên thông với điểm (1, 1) thành giá trị 2.

#include <iostream>
#include <vector>

// Mảng lưu trữ thay đổi chỉ số hàng và cột cho 4 hướng: Lên, Xuống, Trái, Phải
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int rows, cols; // Kích thước mảng

void flood_fill_dfs(int r, int c, int old_value, int new_value, vector<vector<int>>& grid) {
    // Kiểm tra điều kiện dừng/biên
    if (r < 0 || r >= rows || c < 0 || c >= cols) {
        return; // Nằm ngoài biên
    }
    if (grid[r][c] != old_value) {
        return; // Không phải giá trị cũ cần loang
    }
    // Nếu đã là new_value rồi thì không cần làm gì nữa (tránh lặp vô hạn nếu old_value == new_value,
    // hoặc nếu bài toán yêu cầu chỉ loang 1 lần)
    // Tuy nhiên, trong flood fill đổi màu, điều kiện grid[r][c] != old_value ở trên đã đủ.

    // Xử lý ô hiện tại: Thay đổi giá trị
    grid[r][c] = new_value;

    // Gọi đệ quy loang sang 4 ô lân cận
    for (int i = 0; i < 4; ++i) {
        int nr = r + dr[i];
        int nc = c + dc[i];
        flood_fill_dfs(nr, nc, old_value, new_value, grid);
    }
}

int main() {
    vector<vector<int>> grid = {
        {1, 1, 1, 1, 1},
        {1, 0, 0, 0, 1},
        {1, 0, 1, 0, 1},
        {1, 0, 0, 0, 1},
        {1, 1, 1, 1, 1}
    };

    rows = grid.size();
    cols = grid[0].size();

    int start_row = 1;
    int start_col = 1;
    int old_value = grid[start_row][start_col]; // Lấy giá trị tại điểm bắt đầu (ở đây là 0)
    int new_value = 2;

    cout << "Mang truoc khi loang:" << endl;
    for (const auto& row : grid) {
        for (int cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }

    // Thực hiện loang từ điểm (1, 1)
    flood_fill_dfs(start_row, start_col, old_value, new_value, grid);

    cout << "\nMang sau khi loang:" << endl;
    for (const auto& row : grid) {
        for (int cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }

    return 0;
}

Giải thích code DFS:

• dr và dc: Hai mảng này giúp chúng ta dễ dàng tính toán tọa độ của 4 ô lân cận từ ô hiện tại $(r, c)$. Ví dụ, (r + dr[0], c + dc[0]) tương ứng với ô phía trên $(r-1, c)$.
• Hàm flood_fill_dfs:
  • Tham số: Tọa độ $(r, c)$ của ô hiện tại, giá trị cũ (old_value) mà ta muốn thay đổi, giá trị mới (new_value) sẽ thay thế, và mảng grid.
  • Điều kiện dừng: Nếu $(r, c)$ nằm ngoài phạm vi của mảng, hoặc giá trị của ô grid[r][c] không phải là old_value, hàm dừng lại (không loang tiếp từ đây).
  • Xử lý: Nếu các điều kiện dừng không thỏa mãn, nghĩa là ô hiện tại hợp lệ để loang. Ta gán grid[r][c] = new_value để đánh dấu ô này đã được xử lý.
  • Đệ quy: Vòng lặp for duyệt qua 4 hướng. Với mỗi hướng, ta tính toán tọa độ ô lân cận $(nr, nc)$ và gọi đệ quy flood_fill_dfs(nr, nc, ...) để tiếp tục quá trình loang từ ô đó. Quá trình này sẽ tự động dừng lại khi gặp các điều kiện dừng đã nêu.

Lưu ý về DFS: Cách tiếp cận đệ quy rất thanh lịch nhưng có thể gặp vấn đề về tràn bộ nhớ stack nếu vùng cần loang quá lớn và sâu.

2. Sử dụng Hàng đợi (Breadth-First Search - BFS)

BFS về bản chất là khám phá theo từng "lớp" các đỉnh. Với kỹ thuật loang, bạn sẽ bắt đầu từ điểm gốc, thăm tất cả các ô lân cận hợp lệ của nó, sau đó thăm tất cả các ô lân cận hợp lệ của các ô lân cận đó, và cứ thế tiếp tục.

Cấu trúc cơ bản của Flood Fill bằng BFS:

1. Khởi tạo một hàng đợi (queue) và đưa điểm bắt đầu $(r, c)$ vào hàng đợi.
2. Đánh dấu điểm bắt đầu đã được thăm (ví dụ: thay đổi giá trị của nó).
3. Trong khi hàng đợi chưa rỗng:
   • Lấy một điểm $(curr_r, curr_c)$ từ đầu hàng đợi ra.
   • Duyệt qua các ô lân cận $(nr, nc)$ của $(curr_r, curr_c)$.
   • Với mỗi ô lân cận:
     • Kiểm tra xem nó có hợp lệ không (nằm trong biên, có giá trị cũ old_value, chưa được thăm/xếp vào hàng đợi).
     • Nếu hợp lệ, thay đổi giá trị của nó thành new_value và thêm nó vào hàng đợi.

Ví dụ minh họa Flood Fill bằng BFS (4 hướng):

Tiếp tục với ví dụ mảng nước/đất, thay đổi vùng nước liên thông với (1, 1) thành giá trị 2, sử dụng BFS.

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for pair

// Mảng lưu trữ thay đổi chỉ số hàng và cột cho 4 hướng
int dr_bfs[] = {-1, 1, 0, 0};
int dc_bfs[] = {0, 0, -1, 1};

int rows_bfs, cols_bfs; // Kích thước mảng

void flood_fill_bfs(int r, int c, int old_value, int new_value, vector<vector<int>>& grid) {
    // Điều kiện ban đầu: Điểm bắt đầu phải hợp lệ
    if (r < 0 || r >= rows_bfs || c < 0 || c >= cols_bfs || grid[r][c] != old_value) {
        return;
    }

    // Nếu giá trị cũ và mới giống nhau, không cần làm gì
    if (old_value == new_value) {
        return;
    }

    queue<pair<int, int>> q;

    // Đưa điểm bắt đầu vào hàng đợi và xử lý nó
    q.push({r, c});
    grid[r][c] = new_value; // Đánh dấu đã thăm/xử lý bằng cách đổi màu ngay

    while (!q.empty()) {
        pair<int, int> current = q.front();
        q.pop();
        int curr_r = current.first;
        int curr_c = current.second;

        // Duyệt qua 4 ô lân cận
        for (int i = 0; i < 4; ++i) {
            int nr = curr_r + dr_bfs[i];
            int nc = curr_c + dc_bfs[i];

            // Kiểm tra ô lân cận có hợp lệ để loang không
            if (nr >= 0 && nr < rows_bfs && nc >= 0 && nc < cols_bfs && grid[nr][nc] == old_value) {
                // Nếu hợp lệ, xử lý nó (đổi màu) và thêm vào hàng đợi
                grid[nr][nc] = new_value;
                q.push({nr, nc});
            }
        }
    }
}

int main() {
    vector<vector<int>> grid_bfs = {
        {1, 1, 1, 1, 1},
        {1, 0, 0, 0, 1},
        {1, 0, 1, 0, 1},
        {1, 0, 0, 0, 1},
        {1, 1, 1, 1, 1}
    };

    rows_bfs = grid_bfs.size();
    cols_bfs = grid_bfs[0].size();

    int start_row_bfs = 1;
    int start_col_bfs = 1;
    int old_value_bfs = grid_bfs[start_row_bfs][start_col_bfs]; // Lấy giá trị tại điểm bắt đầu (ở đây là 0)
    int new_value_bfs = 2;

    cout << "Mang truoc khi loang (BFS):" << endl;
    for (const auto& row : grid_bfs) {
        for (int cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }

    // Thực hiện loang từ điểm (1, 1)
    flood_fill_bfs(start_row_bfs, start_col_bfs, old_value_bfs, new_value_bfs, grid_bfs);

    cout << "\nMang sau khi loang (BFS):" << endl;
    for (const auto& row : grid_bfs) {
        for (int cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }

    return 0;
}

Giải thích code BFS:

• queue<pair<int, int>> q;: Chúng ta sử dụng một hàng đợi để lưu trữ các tọa độ $(r, c)$ cần thăm. pair rất tiện để lưu trữ cặp tọa độ này.
• Đẩy điểm bắt đầu: Điểm bắt đầu được đưa vào hàng đợi đầu tiên.
• Vòng lặp while (!q.empty()): Vòng lặp này tiếp tục cho đến khi không còn ô nào cần thăm trong hàng đợi.
• q.front() và q.pop(): Lấy ô ở đầu hàng đợi ra để xử lý.
• Kiểm tra ô lân cận: Duyệt qua 4 hướng tương tự như DFS. Điều kiện grid[nr][nc] == old_value là quan trọng để đảm bảo ta chỉ loang vào các ô có giá trị ban đầu giống với vùng cần loang và chưa bị đổi màu (vì khi đổi màu thành new_value, nó sẽ không còn bằng old_value nữa).
• Đẩy vào hàng đợi: Nếu ô lân cận hợp lệ, ta đổi màu nó thành new_value và đẩy tọa độ của nó vào hàng đợi để xử lý sau.

So sánh DFS và BFS trong Flood Fill:

• DFS (Đệ quy): Code thường ngắn gọn hơn, đặc biệt cho những người quen thuộc với đệ quy. Tuy nhiên, có nguy cơ tràn bộ nhớ stack với các vùng loang lớn.
• BFS (Hàng đợi): Sử dụng bộ nhớ heap cho hàng đợi, ít bị giới hạn bởi stack size. Đảm bảo khám phá theo từng lớp, có thể hữu ích trong một số bài toán (mặc dù trong Flood Fill cơ bản thì không quá khác biệt về kết quả cuối cùng so với DFS). Code tường minh hơn về luồng xử lý (iterative).

Cả hai cách tiếp cận đều cho kết quả đúng cho bài toán Flood Fill cơ bản là đổi màu một vùng liên thông. Việc chọn cách nào thường phụ thuộc vào sở thích cá nhân, giới hạn bộ nhớ stack (đối với DFS), hoặc yêu cầu cụ thể của bài toán.

Ứng dụng Thực tế và Biến thể

Kỹ thuật loang không chỉ dừng lại ở việc đổi màu đơn giản. Nó là nền tảng cho nhiều bài toán khác trên lưới:

• Đếm số lượng thành phần liên thông (Connected Components): Ví dụ, đếm số lượng "hòn đảo" trong bản đồ. Bạn có thể duyệt qua từng ô của lưới. Nếu gặp một ô "đất" (chưa được thăm), tăng bộ đếm số đảo lên 1 và sau đó dùng Flood Fill (DFS hoặc BFS) để "thăm" hết toàn bộ hòn đảo đó (bằng cách đổi giá trị của các ô "đất" trong đảo đó thành một giá trị khác, ví dụ -1, để đánh dấu là đã thăm).
• Tìm vùng liên thông lớn nhất: Tương tự như đếm số thành phần, nhưng trong quá trình loang, bạn đếm số ô đã thăm. Sau khi loang xong một vùng, cập nhật kích thước lớn nhất tìm được.
• Kiểm tra đường đi: Trong mê cung hoặc bản đồ, bạn có thể dùng biến thể của Flood Fill (hoặc BFS/DFS nói chung) để xem có đường đi từ điểm A đến điểm B qua các ô hợp lệ không.

Ví dụ: Đếm số "hòn đảo" bằng DFS (biến thể Flood Fill)

Giả sử mảng 2 chiều chứa 1 là đất, 0 là nước. Hai ô đất kề nhau theo 4 hướng tạo thành một hòn đảo.

#include <iostream>
#include <vector>

int dr_island[] = {-1, 1, 0, 0};
int dc_island[] = {0, 0, -1, 1};

int rows_island, cols_island;

// Hàm DFS để "thăm" và đánh dấu một hòn đảo
void visit_island_dfs(int r, int c, vector<vector<int>>& grid) {
    // Kiểm tra biên
    if (r < 0 || r >= rows_island || c < 0 || c >= cols_island) {
        return;
    }
    // Kiểm tra nếu không phải đất (giá trị 1) hoặc đã được thăm (giá trị khác 1)
    if (grid[r][c] != 1) {
        return;
    }

    // Đánh dấu ô hiện tại đã được thăm (ví dụ, đổi thành 2 hoặc -1)
    grid[r][c] = 2;

    // Loang sang các ô lân cận
    for (int i = 0; i < 4; ++i) {
        int nr = r + dr_island[i];
        int nc = c + dc_island[i];
        visit_island_dfs(nr, nc, grid); // Gọi đệ quy
    }
}

int count_islands(vector<vector<int>>& grid) {
    rows_island = grid.size();
    if (rows_island == 0) return 0;
    cols_island = grid[0].size();
    if (cols_island == 0) return 0;

    int count = 0;
    for (int i = 0; i < rows_island; ++i) {
        for (int j = 0; j < cols_island; ++j) {
            // Nếu gặp một ô đất (giá trị 1) chưa được thăm
            if (grid[i][j] == 1) {
                count++; // Tăng số lượng đảo
                // Dùng DFS để thăm hết toàn bộ hòn đảo này và đánh dấu
                visit_island_dfs(i, j, grid);
            }
        }
    }
    return count;
}

int main() {
    vector<vector<int>> grid_island = {
        {0, 1, 0, 0, 0},
        {1, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 0, 1, 1}
    };

    cout << "Mang ban dau:" << endl;
    for (const auto& row : grid_island) {
        for (int cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }

    int num_islands = count_islands(grid_island);

    cout << "\nSo luong dao: " << num_islands << endl;

    // Mảng sau khi chạy count_islands sẽ bị thay đổi (các ô đất đã được đánh dấu)
    cout << "\nMang sau khi danh dau cac dao (o dat=2):" << endl;
     for (const auto& row : grid_island) {
        for (int cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }


    return 0;
}

Giải thích code đếm đảo:

• Hàm count_islands: Duyệt qua từng ô trong lưới. Nếu gặp một ô có giá trị 1 (đất) chưa được thăm (vì hàm visit_island_dfs sẽ đổi giá trị của ô đất thành 2 sau khi thăm), ta biết rằng đây là khởi đầu của một hòn đảo mới. Tăng biến count lên 1 và gọi visit_island_dfs từ ô này.
• Hàm visit_island_dfs: Chức năng tương tự như Flood Fill cơ bản, nhưng điều kiện loang là grid[r][c] == 1. Khi thăm một ô, ta đổi giá trị của nó thành 2 để đánh dấu là đã thăm và không xử lý lại. Hàm này đảm bảo rằng tất cả các ô "đất" liên thông trong cùng một hòn đảo sẽ được thăm hết chỉ từ một lần gọi ban đầu.

Bài tập ví dụ: C++ Bài 11.A4: Đường chéo chính, đường chép phụ

Cho một mảng số nguyên A có \(n\) dòng và \(n\) cột. Hãy tính tổng đường chéo chính, đường chéo phụ.

Minh họa đường chéo chính (đỏ), đường chéo phụ (xanh)

INPUT FORMAT

Dòng đầu tiên nhập vào hai số nguyên dương \(n(1 \leq n\leq 10^3)\).

\(N\) dòng tiếp theo mỗi dòng nhập \(n\) số nguyên là giá trị của \(a_{i,j} (a_{i,j} \leq 10^3)\).

OUTPUT FORMAT

Dòng đầu tiên in ra tổng đường chéo chính.

Dòng thứ 2 in ra tổng đường chéo phụ.

Ví dụ 1:

Input

3 3    
1 7 3
7 4 5
3 5 6

Ouput

11
10

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

Tính tổng các phần tử trên đường chéo chính (từ góc trên trái đến góc dưới phải) và đường chéo phụ (từ góc trên phải đến góc dưới trái) của ma trận.

<br>

1. Bao gồm các thư viện cần thiết:

   • Bạn sẽ cần thư viện để xử lý nhập xuất (iostream).
   • Để lưu trữ ma trận một cách linh hoạt với kích thước được đọc từ input, vector là lựa chọn tốt (vector).

2. Đọc kích thước ma trận:

   • Đọc số nguyên n từ dòng đầu tiên. Kích thước này sẽ xác định số dòng và số cột của ma trận vuông.

3. Khởi tạo biến tổng:

   • Tạo hai biến kiểu số nguyên (ví dụ: long long để đảm bảo không bị tràn số nếu n và giá trị phần tử lớn, mặc dù với giới hạn 1000 thì int cũng đủ trong hầu hết trường hợp) để lưu tổng đường chéo chính và tổng đường chéo phụ. Khởi tạo chúng bằng 0.

4. Lưu trữ và xử lý ma trận:

   • Sử dụng một mảng 2 chiều hoặc vector<vector<int>> có kích thước n x n để lưu trữ các phần tử của ma trận. vector<vector<int>> matrix(n, vector<int>(n)); là cách hiện đại và an toàn.
   • Sử dụng hai vòng lặp lồng nhau để duyệt qua từng phần tử của ma trận. Vòng lặp ngoài điều khiển chỉ số dòng (từ 0 đến n-1), vòng lặp trong điều khiển chỉ số cột (từ 0 đến n-1).
   • Trong các vòng lặp này, đọc giá trị của phần tử tại vị trí hiện tại (dòng i, cột j).
   • Ngay sau khi đọc một phần tử, hãy kiểm tra vị trí của nó để xem nó thuộc đường chéo nào:
     • Đường chéo chính: Một phần tử a[i][j] nằm trên đường chéo chính nếu chỉ số dòng i bằng chỉ số cột j (i == j). Nếu đúng, cộng giá trị của phần tử này vào biến tổng đường chéo chính.
     • Đường chéo phụ: Một phần tử a[i][j] nằm trên đường chéo phụ nếu tổng chỉ số dòng i và chỉ số cột j bằng n - 1 (i + j == n - 1). Nếu đúng, cộng giá trị của phần tử này vào biến tổng đường chéo phụ.

5. In kết quả:

   • Sau khi đã duyệt và xử lý hết tất cả các phần tử của ma trận, in giá trị của biến tổng đường chéo chính ra dòng đầu tiên.
   • In giá trị của biến tổng đường chéo phụ ra dòng thứ hai.
   • Sử dụng cin và cout để thực hiện nhập xuất.

Ghi chú:

• Đảm bảo bạn sử dụng chỉ số mảng/vector bắt đầu từ 0.
• Đối với ma trận kích thước lớn (n=1000), việc sử dụng vector và cấp phát động là phù hợp hơn mảng tĩnh lớn trên stack.
• Nếu n là số lẻ, phần tử chính giữa của ma trận sẽ nằm trên cả hai đường chéo. Cách kiểm tra i == j và i + j == n - 1 độc lập sẽ tự động cộng phần tử này vào cả hai tổng, đây là cách tính đúng theo đề bài.

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