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

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:

1. Mảng 2 chiều (Grid): Dữ liệu mà chúng ta sẽ thao tác trên đó.
2. Điểm bắt đầu (Start Point): Ô đầu tiên mà quá trình loang xuất phát.
3. Đ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).
4. 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.
5. 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> // Dù ví dụ 1 dùng DFS, ta cứ include sẵn để tiện cho các ví dụ sau

// Mảng 2 chiều ví dụ
vector<vector<int>> image = {
    {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 rows = image.size();
int cols = image[0].size();

// 4 hướng di chuyển: lên, xuống, trái, phải
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

// Hàm DFS thực hiện loang
void flood_fill_dfs(int r, int c, int oldColor, int newColor) {
    // 1. Kiểm tra điều kiện dừng/biên:
    // - Nếu nằm ngoài biên của mảng
    // - Nếu ô hiện tại không có màu cũ (không phải vùng cần đổi màu)
    if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] != oldColor) {
        return; // Dừng đệ quy
    }

    // 2. Đổi màu ô hiện tại
    image[r][c] = newColor;

    // 3. Đệ quy gọi hàm flood_fill_dfs cho các ô lân cận (4 hướng)
    for (int i = 0; i < 4; ++i) {
        int nr = r + dr[i]; // Hàng của ô lân cận
        int nc = c + dc[i]; // Cột của ô lân cận
        flood_fill_dfs(nr, nc, oldColor, newColor);
    }
}

// Hàm in mảng
void print_image() {
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            cout << image[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

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

    // Loang tu vi tri (2, 2), mau cu la 0, mau moi la 9
    int startRow = 2;
    int startCol = 2;
    int oldColor = image[startRow][startCol]; // Lay mau cua diem bat dau
    int newColor = 9;

    cout << "Loang tu (" << startRow << ", " << startCol << ") voi mau moi " << newColor << " (mau cu la " << oldColor << ")" << endl;
    flood_fill_dfs(startRow, startCol, oldColor, newColor);

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

    return 0;
}

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

1. Dòng kiểm tra if (r < 0 || r >= rows || c < 0 || c >= cols || image[r][c] != oldColor) 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.
2. Nếu ô hiện tại hợp lệ và có màu oldColor, chúng ta đổi màu nó thành newColor: image[r][c] = newColor;.
3. 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 dr và dc. Đối với mỗi hướng, chúng ta tính tọa độ của ô lân cận (nr, nc) và gọi đệ quy flood_fill_dfs(nr, nc, oldColor, newColor). 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 oldColor.

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.

Lưu ý: Trong ví dụ này, chúng ta không cần mảng visited riêng vì việc đổi màu trực tiếp trên mảng image đã ngầm đánh dấu các ô đã được thăm (chúng sẽ không còn màu oldColor 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 visited 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 visited để giải quyết bài toán này.

#include <iostream>
#include <vector>
#include <string> // Sử dụng string cho hàng của grid

// Grid ví dụ: '1' là đất (đảo), '0' là nước
vector<string> grid = {
    {"11000"},
    {"11000"},
    {"00100"},
    {"00011"}
};

int numRows = grid.size();
int numCols = grid[0].size();

// Mảng đánh dấu đã thăm
vector<vector<bool>> visited;

// 4 hướng di chuyển
int d_r[] = {-1, 1, 0, 0};
int d_c[] = {0, 0, -1, 1};

// Hàm DFS để thăm và đánh dấu toàn bộ một đảo
void dfs_count_islands(int r, int c) {
    // 1. Kiểm tra điều kiện dừng/biên:
    // - Nằm ngoài biên
    // - Đã thăm rồi
    // - Không phải là đất ('1')
    if (r < 0 || r >= numRows || c < 0 || c >= numCols || visited[r][c] || grid[r][c] == '0') {
        return;
    }

    // 2. Đánh dấu ô hiện tại đã thăm
    visited[r][c] = true;

    // 3. Đệ quy gọi cho các ô lân cận
    for (int i = 0; i < 4; ++i) {
        int nr = r + d_r[i];
        int nc = c + d_c[i];
        dfs_count_islands(nr, nc);
    }
}

int main() {
    // Khởi tạo mảng visited với giá trị false ban đầu
    visited.resize(numRows, vector<bool>(numCols, false));

    int islandCount = 0;

    // Duyệt qua từng ô trong grid
    for (int i = 0; i < numRows; ++i) {
        for (int j = 0; j < numCols; ++j) {
            // Nếu ô này là đất ('1') và chưa được thăm
            if (grid[i][j] == '1' && !visited[i][j]) {
                // Chúng ta tìm thấy một hòn đảo mới!
                islandCount++;
                // Bắt đầu loang (DFS) từ đây để đánh dấu toàn bộ hòn đảo này
                dfs_count_islands(i, j);
            }
        }
    }

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

    return 0;
}

Giải thích code: Chúng ta có mảng visited để theo dõi các ô đã được thăm trong quá trình loang. Hàm dfs_count_islands tương tự như flood_fill_dfs nhưng thay vì đổi màu, nó chỉ đánh dấu ô hiện tại là visited[r][c] = 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 (!visited[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 islandCount và gọi dfs_count_islands(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 visited, đảm bảo mỗi hòn đảo chỉ được đếm một lần.

Output sẽ là: 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> // Cho pair

// Grid ví dụ: 0 là đường đi, 1 là chướng ngại vật
vector<vector<int>> grid_path = {
    {0, 0, 0, 0},
    {1, 1, 0, 0},
    {0, 0, 0, 1},
    {0, 1, 0, 0}
};

int gridRows = grid_path.size();
int gridCols = grid_path[0].size();

// 4 hướng di chuyển
int path_dr[] = {-1, 1, 0, 0};
int path_dc[] = {0, 0, -1, 1};

// Hàm BFS để tìm đường đi ngắn nhất
int bfs_shortest_path(int startR, int startC, int endR, int endC) {
    // Nếu điểm bắt đầu hoặc kết thúc là chướng ngại vật
    if (grid_path[startR][startC] == 1 || grid_path[endR][endC] == 1) {
        return -1; // Không thể đi
    }

    // Hàng đợi cho BFS. Mỗi phần tử là một pair {tọa độ, khoảng cách}
    queue<pair<pair<int, int>, int>> q;

    // Mảng lưu khoảng cách từ điểm bắt đầu đến mỗi ô
    // Ban đầu gán -1 cho tất cả các ô (chưa thăm)
    vector<vector<int>> dist(gridRows, vector<int>(gridCols, -1));

    // Thêm điểm bắt đầu vào hàng đợi và gán khoảng cách là 0
    q.push({{startR, startC}, 0});
    dist[startR][startC] = 0;

    // Bắt đầu quá trình BFS
    while (!q.empty()) {
        // Lấy phần tử đầu hàng đợi
        pair<pair<int, int>, int> current = q.front();
        q.pop();

        int r = current.first.first;
        int c = current.first.second;
        int d = current.second; // Khoảng cách đến ô hiện tại

        // Nếu đến được điểm kết thúc, trả về khoảng cách
        if (r == endR && c == endC) {
            return d;
        }

        // Duyệt các ô lân cận
        for (int i = 0; i < 4; ++i) {
            int nr = r + path_dr[i];
            int nc = c + path_dc[i];

            // Kiểm tra điều kiện:
            // - Nằm trong biên
            // - Không phải chướng ngại vật (giá trị 0)
            // - Chưa được thăm (khoảng cách vẫn là -1)
            if (nr >= 0 && nr < gridRows && nc >= 0 && nc < gridCols && grid_path[nr][nc] == 0 && dist[nr][nc] == -1) {
                // Đánh dấu đã thăm (gán khoảng cách) và thêm vào hàng đợi
                dist[nr][nc] = d + 1; // Khoảng cách của ô lân cận = khoảng cách ô hiện tại + 1
                q.push({{nr, nc}, d + 1});
            }
        }
    }

    // Nếu hàng đợi rỗng mà chưa đến được đích, nghĩa là không có đường đi
    return -1;
}

int main() {
    int startR = 0, startC = 0;
    int endR = 3, endC = 2;

    cout << "Tim duong di ngan nhat tu (" << startR << ", " << startC << ") den (" << endR << ", " << endC << ")" << endl;

    int shortestDist = bfs_shortest_path(startR, startC, endR, endC);

    if (shortestDist != -1) {
        cout << "Do dai duong di ngan nhat: " << shortestDist << 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 độ (r, c) mà còn lưu cả khoảng cách d từ điểm bắt đầu đến ô đó. Mảng dist được dùng để lưu khoảng cách đến từng ô và cũng ngầm đóng vai trò như mảng visited (ô nào có dist != -1 là đã thăm).

1. Khởi tạo queue với điểm bắt đầu và khoảng cách 0.
2. Vòng lặp while (!q.empty()) tiếp tục cho đến khi hết các ô có thể thăm.
3. Trong mỗi bước lặp, chúng ta lấy một ô từ đầu hàng đợi.
4. Nếu ô đó là đích, chúng ta trả về khoảng cách hiện tại của nó.
5. 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ó (d + 1), gán vào mảng dist, 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

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.