Bài 27.3: Bài tập thực hành loang trên mảng 2 chiều trong C++

Chào mừng các bạn quay trở lại với series học C++ của FullhouseDev! Hôm nay, chúng ta sẽ cùng đào sâu vào một kỹ thuật cực kỳ quan trọng và thú vị khi làm việc với mảng 2 chiều: kỹ thuật "loang", hay còn gọi là Flood Fill. Kỹ thuật này xuất hiện rất nhiều trong các bài toán thực tế, từ xử lý ảnh đơn giản, các trò chơi dạng grid, cho đến các bài toán trên đồ thị được biểu diễn bằng ma trận kề.

Vậy "loang" là gì? Hãy tưởng tượng bạn đổ một ít nước (hoặc sơn) vào một ô trên một lưới ô vuông. Nước/sơn sẽ lan ra các ô lân cận nếu chúng có thể đi qua (ví dụ: không bị chặn bởi tường hoặc có cùng "màu" ban đầu). Kỹ thuật loang trong lập trình chính là mô phỏng quá trình lan truyền này một cách có hệ thống. Chúng ta bắt đầu từ một điểm, và thăm tất cả các điểm "liên thông" với nó dựa trên một điều kiện nhất định.

Ứng dụng của loang thì vô vàn:

Đổ màu trong các phần mềm đồ họa (như Paint).
Tìm kiếm và đếm số lượng các vùng liên thông (ví dụ: các "hòn đảo" trên bản đồ).
Tìm đường đi ngắn nhất trên lưới (với biến thể BFS).
Phân tích cấu trúc trên lưới (ví dụ: các khu vực đóng kín).

Về cơ bản, kỹ thuật loang sử dụng các giải thuật duyệt đồ thị quen thuộc: Depth First Search (DFS) và Breadth First Search (BFS). Mảng 2 chiều của chúng ta lúc này được xem như một đồ thị, trong đó mỗi ô là một đỉnh, và các cạnh nối các đỉnh kề nhau (thường là 4 hướng: lên, xuống, trái, phải, hoặc 8 hướng bao gồm cả đường chéo).

Để thực hiện loang, chúng ta cần những thứ sau:

Mảng 2 chiều (Grid): Dữ liệu mà chúng ta sẽ thao tác trên đó.
Điểm bắt đầu (Start Point): Ô đầu tiên mà quá trình loang xuất phát.
Điều kiện lan truyền (Condition): Quy định khi nào thì nước/sơn có thể lan từ ô hiện tại sang ô lân cận (ví dụ: ô lân cận có cùng giá trị với ô ban đầu, hoặc ô lân cận không phải là chướng ngại vật).
Cơ chế đánh dấu (Marking Mechanism): Để biết ô nào đã được thăm rồi, tránh việc lặp lại vô hạn và đảm bảo mỗi ô chỉ được xử lý một lần. Một mảng boolean visited song song là cách phổ biến nhất.
Hướng di chuyển (Movement Directions): Xác định các ô lân cận là những ô nào (4 hướng hay 8 hướng).

Chúng ta sẽ cùng khám phá sức mạnh của kỹ thuật loang qua các ví dụ cụ thể sử dụng C++.

Ví dụ 1: Flood Fill cơ bản - Đổ màu một vùng liên thông

Bài toán kinh điển nhất của loang chính là Flood Fill: cho một mảng 2 chiều biểu diễn một "bức tranh" (ví dụ: các số hoặc ký tự), một điểm bắt đầu (r, c), một "màu" cũ oldColor (giá trị của ô (r, c) ban đầu), và một "màu" mới newColor. Hãy thay đổi màu của ô (r, c) và tất cả các ô liên thông với nó có cùng màu oldColor thành newColor.

Chúng ta có thể sử dụng DFS cho bài toán này một cách tự nhiên nhờ đệ quy.

#include <iostream>
#include <vector>
#include <queue> 

using namespace std;

vector<vector<int>> a = {
    {1, 1, 1, 1, 1},
    {1, 1, 0, 1, 1},
    {1, 0, 0, 0, 1},
    {1, 1, 0, 1, 1},
    {1, 1, 1, 1, 1}
};

int R = a.size();
int C = a[0].size();

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void loang_dfs(int x, int y, int mc, int mm) {
    if (x < 0 || x >= R || y < 0 || y >= C || a[x][y] != mc) {
        return;
    }

    a[x][y] = mm;

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        loang_dfs(nx, ny, mc, mm);
    }
}

void in_a() {
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    cout << "Hinh anh ban dau:" << endl;
    in_a();

    int sx = 2;
    int sy = 2;
    int mc = a[sx][sy];
    int mm = 9;

    cout << "Loang tu (" << sx << ", " << sy << ") voi mau moi " << mm << " (mau cu la " << mc << ")" << endl;
    loang_dfs(sx, sy, mc, mm);

    cout << "Hinh anh sau khi loang:" << endl;
    in_a();

    return 0;
}

Giải thích code: Chúng ta có một hàm loang_dfs nhận vào tọa độ (x, y) của ô hiện tại, màu cũ mc cần thay thế và màu mới mm.

Dòng kiểm tra if (x < 0 || x >= R || y < 0 || y >= C || a[x][y] != mc) là điểm mấu chốt của đệ quy: Nó kiểm tra xem chúng ta có đang ở trong phạm vi mảng và ô hiện tại có đúng màu mà chúng ta muốn loang hay không. Nếu một trong các điều kiện này không thỏa mãn, tức là chúng ta không nên xử lý ô này, hàm sẽ return và dừng nhánh đệ quy này lại.
Nếu ô hiện tại hợp lệ và có màu mc, chúng ta đổi màu nó thành mm: a[x][y] = mm;.
Vòng lặp for (int i = 0; i < 4; ++i) duyệt qua 4 hướng lân cận sử dụng mảng dx và dy. Đối với mỗi hướng, chúng ta tính tọa độ của ô lân cận (nx, ny) và gọi đệ quy loang_dfs(nx, ny, mc, mm). Quá trình này sẽ tiếp tục lan truyền cho đến khi gặp biên mảng hoặc gặp các ô không có màu mc.

Output của đoạn code trên sẽ cho thấy vùng số 0 xung quanh điểm (2,2) đã được thay thế bằng số 9.

Hinh anh ban dau:
1 1 1 1 1 
1 1 0 1 1 
1 0 0 0 1 
1 1 0 1 1 
1 1 1 1 1 

Loang tu (2, 2) voi mau moi 9 (mau cu la 0)
Hinh anh sau khi loang:
1 1 1 1 1 
1 1 9 1 1 
1 9 9 9 1 
1 1 9 1 1 
1 1 1 1 1

Lưu ý: Trong ví dụ này, chúng ta không cần mảng tham riêng vì việc đổi màu trực tiếp trên mảng a đã ngầm đánh dấu các ô đã được thăm (chúng sẽ không còn màu mc nữa). Tuy nhiên, trong các bài toán khác khi không được phép thay đổi dữ liệu gốc, hoặc điều kiện loang phức tạp hơn, việc sử dụng mảng tham là cần thiết.

Ví dụ 2: Đếm số lượng vùng liên thông (Đếm đảo)

Một bài toán rất phổ biến khác sử dụng kỹ thuật loang là đếm số lượng các "vùng" hoặc "cụm" liên thông thỏa mãn một điều kiện nhất định. Ví dụ, trên một bản đồ 0-1, chúng ta muốn đếm số lượng các "hòn đảo" (cụm các ô 1 liên thông).

Chúng ta sẽ sử dụng DFS kết hợp với mảng tham để giải quyết bài toán này.

#include <iostream>
#include <vector>
#include <string> 

using namespace std;

vector<string> a = {
    {"11000"},
    {"11000"},
    {"00100"},
    {"00011"}
};

int R = a.size();
int C = a[0].size();

vector<vector<bool>> tham;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs_dem_dao(int x, int y) {
    if (x < 0 || x >= R || y < 0 || y >= C || tham[x][y] || a[x][y] == '0') {
        return;
    }

    tham[x][y] = true;

    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        dfs_dem_dao(nx, ny);
    }
}

int main() {
    tham.resize(R, vector<bool>(C, false));

    int so_dao = 0;

    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (a[i][j] == '1' && !tham[i][j]) {
                so_dao++;
                dfs_dem_dao(i, j);
            }
        }
    }

    cout << "So luong dao tim thay: " << so_dao << endl;

    return 0;
}

Giải thích code: Chúng ta có mảng tham để theo dõi các ô đã được thăm trong quá trình loang. Hàm dfs_dem_dao tương tự như loang_dfs nhưng thay vì đổi màu, nó chỉ đánh dấu ô hiện tại là tham[x][y] = true; và tiếp tục loang sang các ô lân cận là đất ('1') và chưa được thăm.

Hàm main là nơi logic chính diễn ra. Chúng ta duyệt qua từng ô (i, j) của grid. Nếu gặp một ô là đất ('1') và chưa được thăm (!tham[i][j]), điều đó có nghĩa là chúng ta vừa đặt chân lên một hòn đảo mới. Chúng ta tăng biến đếm so_dao và gọi dfs_dem_dao(i, j) để thăm toàn bộ các ô đất liên thông của hòn đảo này, đánh dấu chúng là đã thăm. Bằng cách này, khi vòng lặp ngoài tiếp tục duyệt, các ô thuộc hòn đảo vừa thăm sẽ bị bỏ qua vì chúng đã được đánh dấu tham, đảm bảo mỗi hòn đảo chỉ được đếm một lần.

Output sẽ là: So luong dao tim thay: 3

So luong dao tim thay: 3

Ví dụ 3: Tìm đường đi ngắn nhất trên lưới (Sử dụng BFS)

Trong khi DFS phù hợp với việc thăm toàn bộ một vùng hoặc đếm số lượng vùng, BFS lại là lựa chọn tối ưu cho các bài toán tìm đường đi ngắn nhất trên lưới (hoặc đồ thị không trọng số), bởi vì nó duyệt qua các đỉnh theo từng "lớp" khoảng cách từ điểm bắt đầu.

Bài toán: Cho một lưới các ô vuông, trong đó một số ô là chướng ngại vật. Tìm độ dài đường đi ngắn nhất từ điểm bắt đầu đến điểm kết thúc.

#include <iostream>
#include <vector>
#include <queue>
#include <utility> 

using namespace std;

vector<vector<int>> a = {
    {0, 0, 0, 0},
    {1, 1, 0, 0},
    {0, 0, 0, 1},
    {0, 1, 0, 0}
};

int R = a.size();
int C = a[0].size();

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int bfs_duong_ngan_nhat(int sx, int sy, int ex, int ey) {
    if (a[sx][sy] == 1 || a[ex][ey] == 1) {
        return -1;
    }

    queue<pair<pair<int, int>, int>> q;
    vector<vector<int>> d(R, vector<int>(C, -1));

    q.push({{sx, sy}, 0});
    d[sx][sy] = 0;

    while (!q.empty()) {
        pair<pair<int, int>, int> hien_tai = q.front();
        q.pop();

        int x = hien_tai.first.first;
        int y = hien_tai.first.second;
        int kc = hien_tai.second;

        if (x == ex && y == ey) {
            return kc;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < R && ny >= 0 && ny < C && a[nx][ny] == 0 && d[nx][ny] == -1) {
                d[nx][ny] = kc + 1;
                q.push({{nx, ny}, kc + 1});
            }
        }
    }

    return -1;
}

int main() {
    int sx = 0, sy = 0;
    int ex = 3, ey = 2;

    cout << "Tim duong di ngan nhat tu (" << sx << ", " << sy << ") den (" << ex << ", " << ey << ")" << endl;

    int kc_ngan_nhat = bfs_duong_ngan_nhat(sx, sy, ex, ey);

    if (kc_ngan_nhat != -1) {
        cout << "Do dai duong di ngan nhat: " << kc_ngan_nhat << endl;
    } else {
        cout << "Khong co duong di den dich." << endl;
    }

    return 0;
}

Giải thích code: Chúng ta sử dụng queue để quản lý các ô cần thăm theo thứ tự lớp. Mỗi phần tử trong queue không chỉ lưu tọa độ (x, y) mà còn lưu cả khoảng cách kc từ điểm bắt đầu đến ô đó. Mảng d được dùng để lưu khoảng cách đến từng ô và cũng ngầm đóng vai trò như mảng tham (ô nào có d != -1 là đã thăm).

Khởi tạo queue với điểm bắt đầu và khoảng cách 0.
Vòng lặp while (!q.empty()) tiếp tục cho đến khi hết các ô có thể thăm.
Trong mỗi bước lặp, chúng ta lấy một ô từ đầu hàng đợi.
Nếu ô đó là đích, chúng ta trả về khoảng cách hiện tại của nó.
Nếu không, chúng ta duyệt các ô lân cận. Đối với mỗi ô lân cận hợp lệ (trong biên, không chướng ngại vật, chưa thăm), chúng ta tính khoảng cách của nó (kc + 1), gán vào mảng d, và thêm nó vào cuối hàng đợi.

Vì BFS thăm các ô theo thứ tự tăng dần của khoảng cách, ô đầu tiên mà chúng ta lấy ra từ hàng đợi và trùng với điểm kết thúc chắc chắn là ô nằm trên đường đi ngắn nhất.

Output sẽ là: Do dai duong di ngan nhat: 6

Tim duong di ngan nhat tu (0, 0) den (3, 2)
Do dai duong di ngan nhat: 6

DFS vs BFS trong kỹ thuật Loang

Cả DFS và BFS đều là những công cụ mạnh mẽ để thực hiện kỹ thuật loang trên mảng 2 chiều, nhưng chúng có những đặc điểm khác nhau:

DFS (Đệ quy hoặc Stack):
- Đi sâu vào một nhánh nhất có thể trước khi quay lại.
- Ưu điểm: Code thường ngắn gọn hơn khi sử dụng đệ quy. Tốn ít bộ nhớ hơn trong trường hợp đồ thị "mảnh" (ít cạnh).
- Nhược điểm: Có thể gây tràn bộ nhớ stack với đồ thị quá sâu (trường hợp mảng 2 chiều rất lớn và đường đi dài). Không đảm bảo tìm được đường đi ngắn nhất.
- Phù hợp: Đếm thành phần liên thông, kiểm tra tính liên thông, tìm tất cả các đường đi (nếu bỏ qua visited sau khi xử lý), Flood Fill đơn giản.
BFS (Hàng đợi - Queue):
- Duyệt từng lớp các đỉnh kề từ điểm bắt đầu.
- Ưu điểm: Luôn tìm được đường đi ngắn nhất trên đồ thị không trọng số (như mảng 2 chiều với chi phí di chuyển giữa các ô kề nhau là 1). Không bị giới hạn bởi độ sâu đệ quy.
- Nhược điểm: Có thể tốn nhiều bộ nhớ hơn vì phải lưu trữ tất cả các đỉnh cùng một "lớp" trong hàng đợi. Code dùng queue thường dài hơn code DFS đệ quy một chút.
- Phù hợp: Tìm đường đi ngắn nhất, tìm kiếm các đỉnh ở khoảng cách k, kiểm tra xem có đường đi hay không.

Trong thực tế, bạn cần dựa vào yêu cầu cụ thể của bài toán để lựa chọn giữa DFS và BFS. Với các bài toán liên quan đến khoảng cách hoặc đường đi ngắn nhất, BFS là sự lựa chọn mặc định. Với các bài toán chỉ cần thăm hết các ô liên thông hoặc đếm số lượng vùng, cả hai đều có thể sử dụng, nhưng DFS đệ quy có thể cho code "dễ nhìn" hơn đối với nhiều người.

Comments

There are no comments at the moment.