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 loang_dfs(int r, int c, int cu, int moi, vector<vector<int>>& a) {
    // Kiem tra bien, gia tri
    // Danh dau da tham
    // Goi de quy lan can
}

Để 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>

using namespace std;

// Hướng di chuyển: trên, dưới, trái, phải
int h[] = {-1, 1, 0, 0};
int c[] = {0, 0, -1, 1};

int R, C; // Kích thước mảng

void loang_dfs(int r, int k, int cu, int moi, vector<vector<int>>& a) {
    if (r < 0 || r >= R || k < 0 || k >= C) return;
    if (a[r][k] != cu) return;

    a[r][k] = moi;

    for (int i = 0; i < 4; ++i) {
        loang_dfs(r + h[i], k + c[i], cu, moi, a);
    }
}

int main() {
    vector<vector<int>> a = {
        {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}
    };

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

    int r0 = 1;
    int k0 = 1;
    int cu = a[r0][k0];
    int moi = 2;

    cout << "Mang truoc khi loang:" << endl;
    for (const auto& dong : a) {
        for (int o : dong) {
            cout << o << " ";
        }
        cout << endl;
    }

    loang_dfs(r0, k0, cu, moi, a);

    cout << "\nMang sau khi loang:" << endl;
    for (const auto& dong : a) {
        for (int o : dong) {
            cout << o << " ";
        }
        cout << endl;
    }

    return 0;
}

Mang truoc khi loang:
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 

Mang sau khi loang:
1 1 1 1 1 
1 2 2 2 1 
1 2 1 2 1 
1 2 2 2 1 
1 1 1 1 1

Giải thích code DFS:

  • h và c: 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 + h[0], k + c[0]) tương ứng với ô phía trên $(r-1, c)$.
  • Hàm loang_dfs:
    • Tham số: Tọa độ $(r, c)$ của ô hiện tại, giá trị cũ (cu) mà ta muốn thay đổi, giá trị mới (moi) sẽ thay thế, và mảng a.
    • Đ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 ô a[r][c] không phải là cu, 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 a[r][c] = moi để đá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 loang_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. Khoi tao hang doi, them diem bat dau.
  2. Danh dau diem bat dau.
  3. Lap khi hang doi chua rong:
    • Lay diem hien tai.
    • Duyet cac o lan can:
      • Kiem tra hop le.
      • Doi gia tri va them vao hang doi.

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

using namespace std;

// Hướng di chuyển: trên, dưới, trái, phải
int h_bfs[] = {-1, 1, 0, 0};
int c_bfs[] = {0, 0, -1, 1};

int R_bfs, C_bfs; // Kích thước mảng

void loang_bfs(int r, int k, int cu, int moi, vector<vector<int>>& a) {
    if (r < 0 || r >= R_bfs || k < 0 || k >= C_bfs || a[r][k] != cu) return;
    if (cu == moi) return;

    queue<pair<int, int>> q;
    q.push({r, k});
    a[r][k] = moi;

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

        for (int i = 0; i < 4; ++i) {
            int nr = hr + h_bfs[i];
            int nc = hc + c_bfs[i];

            if (nr >= 0 && nr < R_bfs && nc >= 0 && nc < C_bfs && a[nr][nc] == cu) {
                a[nr][nc] = moi;
                q.push({nr, nc});
            }
        }
    }
}

int main() {
    vector<vector<int>> a_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}
    };

    R_bfs = a_bfs.size();
    C_bfs = a_bfs[0].size();

    int r0_bfs = 1;
    int k0_bfs = 1;
    int cu_bfs = a_bfs[r0_bfs][k0_bfs];
    int moi_bfs = 2;

    cout << "Mang truoc khi loang (BFS):" << endl;
    for (const auto& dong : a_bfs) {
        for (int o : dong) {
            cout << o << " ";
        }
        cout << endl;
    }

    loang_bfs(r0_bfs, k0_bfs, cu_bfs, moi_bfs, a_bfs);

    cout << "\nMang sau khi loang (BFS):" << endl;
    for (const auto& dong : a_bfs) {
        for (int o : dong) {
            cout << o << " ";
        }
        cout << endl;
    }

    return 0;
}

Mang truoc khi loang (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 

Mang sau khi loang (BFS):
1 1 1 1 1 
1 2 2 2 1 
1 2 1 2 1 
1 2 2 2 1 
1 1 1 1 1

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 a[nr][nc] == cu 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 moi, nó sẽ không còn bằng cu nữa).
  • Đẩy vào hàng đợi: Nếu ô lân cận hợp lệ, ta đổi màu nó thành moi 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>

using namespace std;

int h_dao[] = {-1, 1, 0, 0};
int c_dao[] = {0, 0, -1, 1};

int R_dao, C_dao;

void tham_dao(int r, int k, vector<vector<int>>& a) {
    if (r < 0 || r >= R_dao || k < 0 || k >= C_dao) return;
    if (a[r][k] != 1) return; // Chỉ thăm đất (1)

    a[r][k] = 2; // Đánh dấu đã thăm

    for (int i = 0; i < 4; ++i) {
        tham_dao(r + h_dao[i], k + c_dao[i], a);
    }
}

int dem_dao(vector<vector<int>>& a) {
    R_dao = a.size();
    if (R_dao == 0) return 0;
    C_dao = a[0].size();
    if (C_dao == 0) return 0;

    int so_dao = 0;
    for (int i = 0; i < R_dao; ++i) {
        for (int j = 0; j < C_dao; ++j) {
            if (a[i][j] == 1) { // Nếu gặp đất chưa thăm
                so_dao++;
                tham_dao(i, j, a); // Thăm hết đảo
            }
        }
    }
    return so_dao;
}

int main() {
    vector<vector<int>> a_dao = {
        {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& dong : a_dao) {
        for (int o : dong) {
            cout << o << " ";
        }
        cout << endl;
    }

    int so_luong_dao = dem_dao(a_dao);

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

    cout << "\nMang sau khi danh dau cac dao (o dat=2):" << endl;
     for (const auto& dong : a_dao) {
        for (int o : dong) {
            cout << o << " ";
        }
        cout << endl;
    }

    return 0;
}

Mang ban dau:
0 1 0 0 0 
1 1 0 0 0 
0 0 1 0 0 
0 0 0 1 1 

So luong dao: 3

Mang sau khi danh dau cac dao (o dat=2):
0 2 0 0 0 
2 2 0 0 0 
0 0 2 0 0 
0 0 0 2 2

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

  • Hàm dem_dao: 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 tham_dao 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 so_dao lên 1 và gọi tham_dao từ ô này.
  • Hàm tham_dao: Chức năng tương tự như Flood Fill cơ bản, nhưng điều kiện loang là a[r][k] == 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ụ 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.

  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.
#include <iostream>
#include <vector>

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // Doc kich thuoc ma tran

    long long chinh = 0; // Tong duong cheo chinh
    long long phu = 0;   // Tong duong cheo phu

    // Luu tru ma tran
    vector<vector<int>> a(n, vector<int>(n));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j]; // Doc gia tri phan tu

            if (i == j) { // Kiem tra duong cheo chinh
                chinh += a[i][j];
            }
            if (i + j == n - 1) { // Kiem tra duong cheo phu
                phu += a[i][j];
            }
        }
    }

    cout << chinh << endl;
    cout << phu << endl;

    return 0;
}

Input:

3 3    
1 7 3
7 4 5
3 5 6

Output:

11
10

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

Comments

There are no comments at the moment.