Hiểu bài toán

Bài toán yêu cầu đếm số lượng các vùng (mảnh giấy) bị tách rời nhau trong một lưới hình chữ nhật. Các ô trong lưới có thể là '#', đại diện cho phần giấy còn lại, hoặc '.', đại diện cho lỗ已被 đục. Hai ô thuộc cùng một mảnh giấy nếu chúng có thể được kết nối với nhau qua các ô '#' kề nhau (theo 4 hướng: trên, dưới, trái, phải). Nói cách khác, bài toán là đếm số thành phần liên thông của các ô '#' trong một lưới 2D.

Các cách tiếp cận

Cách Depth First Search (DFS) - Dùng mảng visited

#include <bits/stdc++.h>
using namespace std;

int m, n;
vector<string> a;
bool vis[105][105];
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

void dfs(int r, int c) {
    vis[r][c] = true;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
            if (!vis[nr][nc] && a[nr][nc] == '#') {
                dfs(nr, nc);
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    a.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!vis[i][j] && a[i][j] == '#') {
                cnt++;
                dfs(i, j);
            }
        }
    }
    cout << cnt;
    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

Đây là cách tiếp cận trực quan nhất. Chúng ta duyệt qua từng ô của lưới. Nếu gặp một ô '#' chưa được thăm (chưa nằm trong một vùng nào), ta bắt đầu một cuộc duyệt DFS từ ô đó. DFS sẽ đánh dấu tất cả các ô '#' có thể đến được từ ô hiện tại là đã thăm. Mỗi lần bắt đầu một DFS mới tương ứng với việc tìm thấy một mảnh giấy mới, do đó ta tăng biến đếm lên 1. Sau khi duyệt hết lưới, biến đếm sẽ chứa số lượng mảnh giấy.

• Lưu ý về chỉ số: Các solution mẫu sử dụng các quy ước chỉ số khác nhau (0-based hoặc 1-based). Code mẫu ở trên dùng 0-based cho tiện với vector<string>. Logic là tương tự nhau, chỉ cần chú ý điều chỉnh điều kiện biên cho phù hợp.

Cách Depth First Search (DFS) - Thay đổi trực tiếp trên lưới

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define TranHungss(); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int maxn = 105;

int n, m;
char a[maxn][maxn];

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

void DFS(int i, int j){
    a[i][j] = '.';
    for(int k = 0; k < 4; k++){
        int i1 = i + dx[k];
        int j1 = j + dy[k];
        if(i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= m && a[i1][j1] == '#'){
            DFS(i1, j1);
        }
    }
}

int main(){
    TranHungss();
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] == '#'){
                ++res;
                DFS(i, j);
            }
        }
    }    
    cout << res << endl;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n) (do đệ quy)

Phương pháp này cũng sử dụng DFS nhưng không cần một mảng vis riêng. Thay vào đó, nó đánh dấu các ô đã thăm bằng cách thay đổi ký tự '#' thành '.' ngay trên lưới. Khi duyệt DFS, nếu gặp một ô '#', nó sẽ được 'xóa' (đánh dấu là '.') và quá trình duyệt sẽ tiếp tục. Ưu điểm của cách này là code ngắn gọn hơn, không cần thêm mảng vis.

Tuy nhiên, nó làm thay đổi dữ liệu đầu vào. Nếu ta cần sử dụng lại lưới sau khi đếm, cách này không phù hợp. Trong bài toán này, chỉ cần đếm số vùng thì nó hoàn toàn thỏa mãn.

Cách Breadth First Search (BFS)

// Pseudocode for BFS approach
#include <bits/stdc++.h>
using namespace std;

int m, n;
vector<string> a;
bool vis[105][105];
int dr[] = {1, -1, 0, 0};
int dc[] = {0, 0, 1, -1};

void bfs(int start_r, int start_c) {
    queue<pair<int, int>> q;
    q.push({start_r, start_c});
    vis[start_r][start_c] = true;

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        int r = cur.first;
        int c = cur.second;

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !vis[nr][nc] && a[nr][nc] == '#') {
                vis[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }
}

int main() {
    cin >> m >> n;
    a.resize(m);
    for (int i = 0; i < m; i++) cin >> a[i];

    int cnt = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (!vis[i][j] && a[i][j] == '#') {
                cnt++;
                bfs(i, j);
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

• Time Complexity: O(m * n)
• Space Complexity: O(m * n)

BFS là một thuật toán duyệt đồ thị khác, hoạt động theo chiều rộng. Nó cũng có thể được dùng để giải quyết bài toán này. Thay vì dùng đệ quy như DFS, BFS sử dụng một hàng đợi (queue). Khi tìm thấy một ô '#' chưa thăm, ta thêm nó vào hàng đợi và bắt đầu vòng lặp: lấy một ô ra, thêm tất cả các ô '#' kề chưa thăm vào hàng đợi và đánh dấu là đã thăm. Quá trình này lặp lại cho đến khi hàng đợi rỗng. Mỗi lần bắt đầu một BFS mới cũng tương ứng với một mảnh giấy mới. Tốc độ và bộ nhớ tương đương DFS.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được mô hình hóa như một bài toán tìm số thành phần liên thông (Connected Components) trong đồ thị 2D, où các ô '#' là các node và các cạnh giữa các ô kề nhau là các cạnh đồ thị.
• Cả DFS và BFS đều là các thuật toán chuẩn để đếm số thành phần liên thông. Mỗi thuật toán có ưu và nhược điểm riêng (DFS code ngắn hơn nhưng có thể tràn bộ nhớ stack nếu đệ quy quá sâu, BFS dùng nhiều bộ nhớ hơn nhưng an toàn hơn về mặt đệ quy).
• Việc sử dụng chính lưới đầu vào để đánh dấu các ô đã thăm (thay '#' bằng '.') là một kỹ thuật tối ưu không gian bộ nhớ, nhưng chỉ phù hợp khi ta không cần giữ lại dữ liệu gốc.

Lỗi thường gặp

• Lỗi chỉ số biên: Khi duyệt các ô kề nhau, cần kiểm tra kỹ xem các chỉ số hàng và cột mới có nằm trong phạm vi hợp lệ của lưới hay không (ví dụ: 0 <= r < m và 0 <= c < n với mảng 0-based).
• Quên đánh dấu ô đã thăm: Nếu không đánh dấu ô đã thăm (bằng mảng vis hoặc thay đổi giá trị trên lưới), một ô có thể được duyệt nhiều lần, dẫn đến đếm sai số vùng hoặc gây ra vòng lặp vô hạn.
• Xử lý input sai: Input có thể có khoảng trắng hoặc newline thừa. Nên dùng cin >> m >> n và cin >> a[i] để tự động bỏ qua khoảng trắng. Nếu dùng getline, cần xử lý newline cẩn thận.