Đồ Thị Lưới 2D, Kỹ Thuật Flood Fill & Tính Chất Cây

1. Bản chất mô hình hóa lưới 2D thành đồ thị

Trong lập trình thi đấu, ma trận bảng vuông $N \times M$ có thể được xem là một đồ thị đặc biệt:

• Mỗi ô $(r, c)$ là một Đỉnh của đồ thị ($1 \le r \le N, 1 \le c \le M$). Tổng số đỉnh $|V| = N \times M$.
• Mỗi bước di chuyển sang các ô kề cạnh (4 hướng: Trên, Dưới, Trái, Phải) tương đương với một Cạnh vô hướng có trọng số bằng 1. Tổng số cạnh $|E| \le 4NM$.
• Ưu điểm vượt trội: Không cần dựng danh sách kề vector<int> adj[], ta duyệt trực tiếp trên ma trận bằng Mảng Hướng Dịch Chuyển (dr, dc).

2. Thuật toán loang (Flood Fill)

• Bản chất: Từ một ô xuất phát $(r_0, c_0)$, thuật toán lan tỏa (bằng DFS hoặc BFS) sang tất cả các ô lân cận có cùng tính chất (cùng màu, ô đất liền không phải nước biển, ô đường đi không có vật cản).
• Điều kiện biên hợp lệ (Boundary Invariant):

bool isValid(int r, int c) {
    return (r >= 1 && r <= n && c >= 1 && c <= m && grid[r][c] != '#' && !visited[r][c]);
}

• Ứng dụng kinh điển: Đếm số lượng hòn đảo (Number of Islands), tính diện tích vùng lớn nhất, tô màu sơn vùng kín, tìm đường thoát khỏi mê cung.

3. Lý thuyết cây trên đồ thị (Tree Properties & invariants)

Cây (Tree) là một dạng đồ thị vô hướng đặc biệt có cấu trúc phân cấp chặt chẽ:

1. Đồ thị liên thông gồm $N$ đỉnh và có đúng $N - 1$ cạnh.
2. Giữa 2 đỉnh bất kỳ trong cây có duy nhất một đường đi đơn.
3. Không chứa bất kỳ chu trình nào.
4. Duyệt cây bằng DFS: Bắt đầu từ gốc root, khi duyệt từ $u$ sang $v$ chỉ cần điều kiện if (v != parent) mà không cần dùng mảng visited!

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy tràn chỉ số biên ma trận (Index Out of Bounds): * Truy cập grid[r + dr[d]][c + dc[d]] trước khi kiểm tra 1 <= r+dr[d] $\le N$ sẽ gây lỗi Segmentation Fault. * Quy tắc an toàn: Luôn kiểm tra tọa độ trong phạm vi $[1, N] \times [1, M]$ trước tiên!
2. Bẫy nhầm lẫn thứ tự tọa độ Hàng và Cột (r vs c, x vs y): * Trong toán học, trục $x$ là ngang, $y$ là dọc. Nhưng trong ma trận máy tính, chỉ số thứ nhất là Hàng (chiều dọc, $N$), chỉ số thứ hai là Cột (chiều ngang, $M$). * Chuẩn hóa đặt tên: Dùng r (row) và c (col) hoặc $dr$ và $dc$ để triệt tiêu hoàn toàn sự nhầm lẫn.
3. Bẫy kích thước ma trận hình chữ nhật (khi $N \ne M$): * Viết nhầm c <= n thay vì c <= m khi ma trận có số hàng khác số cột sẽ dẫn đến truy cập sai vùng nhớ hoặc đọc thiếu dữ liệu.

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Đếm số lượng hòn đảo và diện tích lớn nhất (Flood Fill DFS)

⚠️ Lưu ý về Stack Overflow: Hàm DFS đệ quy trên lưới 2D có thể gây tràn ngăn xếp hệ thống khi hòn đảo có kích thước lớn (ví dụ lưới $500 \times 500$ toàn ô đất tạo ra độ sâu đệ quy $250{,}000$ tầng). Trong thi đấu thực tế với lưới lớn ($N \times M \ge 10^5$), nên dùng BFS bằng std::queue (xem Mẫu 2 bên dưới) để tránh hoàn toàn rủi ro này. Mẫu DFS đệ quy được giữ lại vì tính trực quan sư phạm.

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

int n, m;
vector<string> grid;

vector<vector<bool>> visited;

const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

bool isValid(int r, int c) {
    return (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] == '1' && !visited[r][c]);
}

int dfs(int r, int c) {
    visited[r][c] = true;
    int area = 1;

    for (int d = 0; d < 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (isValid(nr, nc)) {
            area += dfs(nr, nc);
        }
    }
    return area;
}

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

    if (!(cin >> n >> m)) return 0;

    if (n <= 0 || m <= 0) return 0;

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

    }

    visited.assign(n, vector<bool>(m, false));
    int island_count = 0;
    int max_area = 0;

    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            if (grid[r][c] == '1' && !visited[r][c]) {
                island_count++;
                max_area = max(max_area, dfs(r, c));
            }
        }
    }

    cout << island_count << " " << max_area << "\n";
    return 0;
}

Mẫu 2: Tìm đường đi ngắn nhất trong mê cung (grid BFS)

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

int n, m;
vector<string> grid;

vector<vector<int>> dist;

const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

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

    if (!(cin >> n >> m)) return 0;

    if (n <= 0 || m <= 0) return 0;

    grid.resize(n);
    int sr = -1, sc = -1, er = -1, ec = -1;

    for (int r = 0; r < n; ++r) {
        cin >> grid[r];

        for (int c = 0; c < m; ++c) {
            if (grid[r][c] == 'S') { sr = r; sc = c; }
            if (grid[r][c] == 'E') { er = r; ec = c; }
        }
    }

    dist.assign(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    dist[sr][sc] = 0;
    q.push({sr, sc});

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        if (r == er && c == ec) break;

        for (int d = 0; d < 4; ++d) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push({nr, nc});
            }
        }
    }

    cout << dist[er][ec] << "\n";
    return 0;
}