# DFS và BFS trên bảng 2D
## 1. Mô tả bài toán điển hình
Bài toàn thường gặp nhất là:
> Cho Cho một bảng (ma trận) 2D kích thước `m x n`, trong đó mỗi ô chứa giá trị `0` hoặc `1`. Hãy đếm số lượng **vùng liên thông** gồm các ô `1`. Hai ô `1` được coi là liên thông nếu có thể đi đến nhau bằng các bước đi lên / xuống / trái / phải.
### Ví dụ:

Input:
1 1 0 0 
1 0 0 1
0 0 1 1
0 0 0 0

Output: 3

Có tất cả 2 vùng liên thông các số 1
## 2. DFS trên bảng 2D - Tìm kiếm theo chiều sâu (Depth First Search)
### Ý tưởng
- Thuật toán bắt đầu tại nút gốc (chọn một số nút tùy ý làm nút gốc trong trường hợp đồ thị) và kiểm tra từng nhánh càng xa càng tốt trước khi quay lui.
- Thuật toán này sẽ dùng ngắn xếp có kích thước tối đa bằng số ô trong bảng 2D.
### Thuật toán:
- Để cài đặt DFS trên bảng 2D, ta cần thực hiện các bước sau:
1. Đẩy giá trị (có thể là khoảng cách từ ô gốc) của ô gốc vào ngắn xếp và kèm theo 1 cặp để thể hiện vị trí của ô đó trên bảng 2D.
2. Lấy top value của ngắn xếp ra để đưa value này vào danh sách đã duyệt và tiếp tục duyệt 4 ô ở xung quanh ô được lấy ra.
3. Nếu 1 ô trong 4 đó được đánh dấu là chưa từng được đi qua thì ta liền đẩy đẩy vị trí của ô này vào ngăn xếp.
4. Quay lại bước 2 tiếp tục cho đến khi ngăn xếp rỗng.
### Độ phức tạp:
- Độ phức tạp thời gian của thuật toán DFS được biểu diễn dưới dạng O(V + E), trong đó V là số nút và E là số cạnh. Độ phức tạp không gian của thuật toán là O(V).
### Ứng dụng:
- Sắp xếp tô pô, schedule problems, phát hiện chu trình trong biểu đồ và giải các câu đố chỉ bằng một giải pháp, chẳng hạn như mê cung hoặc câu đố sudoku, tất cả đều sử dụng tìm kiếm theo chiều sâu.
- Các ứng dụng khác liên quan đến phân tích mạng, chẳng hạn như phát hiện xem biểu đồ có phải là bipartite không.
- DFS cũng được sử dụng như một chương trình con trong các thuật toán matching trong lý thuyết đồ thị như thuật toán Hopcroft-Karp.
- Tìm kiếm theo chiều sâu được sử dụng trong lập route mapping, scheduling và tìm cây khung.
## 3. BFS trên bảng 2D - Tìm kiếm theo chiều rộng (Breadth First Search)
### Ý tưởng:
- Tìm kiếm theo chiều rộng (BFS) là một thuật toán để duyệt đồ thị hoặc cây.
- BFS áp dụng cho cây và đồ thị gần như giống nhau. Sự khác biệt duy nhất là đồ thị có thể chứa các chu trình, vì vậy chúng ta có thể duyệt lại cùng một nút.
- Để tránh xử lý lại cùng một nút, chúng ta sử dụng mảng boolean đã truy cập, mảng này sẽ đánh dấu các đỉnh đã truy cập.
- BFS sử dụng cấu trúc dữ liệu hàng đợi (queue) để tìm đường đi ngắn nhất trong biểu đồ.
### Thuật toán:
- Cách thuật toán hoạt động trên bảng 2D như sau:
1. Lấy một ô bất kỳ trong bảng thêm vào cuối hàng đợi.
2. Lấy phân tử đầu tiên của hàng đợi và thêm nó vào danh sách đã duyệt.
3. Tạo một danh sách các ô liền kề của ô đang xét. Thêm những ô không có trong danh sách đã duyệt vào cuối hàng đợi.
4. Tiếp tục lặp lại bước 2 và 3 cho đến khi hàng đợi trống.
### Độ phức tạp:
- Độ phức tạp thời gian của thuật toán BFS được biểu diễn dưới dạng O(V + E), trong đó V là số nút và E là số cạnh.
- Độ phức tạp không gian của thuật toán là O(V).
### Ứng dụng:
- Trình thu thập dữ liệu trong Công cụ Tìm kiếm: Tìm kiếm theo chiều rộng là thuật toán chính được sử dụng để lập chỉ mục các trang web. Thuật toán BFS bắt đầu từ trang nguồn và đi theo tất cả các liên kết được liên kết với nó.
- Mạng peer-to-peer: Tìm kiếm theo chiều rộng có thể được sử dụng để tìm tất cả các nút lân cận trong mạng peer-to-peer. Ví dụ: BitTorrent sử dụng BFS để giao tiếp peer-to-peer.
- Hệ thống định vị GPS: Thuật toán tốt nhất để xác định đường đi ngắn nhất từ vị trí này đến vị trí khác là tìm kiếm theo chiều rộng.
- Thuật toán Ford-Fulkerson: Để tìm luồng cực đại trong mạng, hãy sử dụng thuật toán Ford-Fulkerson.
- Đường đi ngắn nhất & cây khung tối thiểu cho đồ thị không trọng số: Tìm kiếm theo chiều rộng được sử dụng để tìm đường đi ngắn nhất & cây khung tối thiểu cho đồ thị không trọng số.
## 4. Bài tập ví dụ
### Bài 1: Đếm số đảo
Cho một bảng `m x n` gồm `1` (đất) và `0` (nước). Một đảo là tập các ô `1` liền nhau theo 4 hướng. Đếm số đảo có trong bảng.
#### Input
- Dòng đầu tiên chứa hai số nguyên $n$ và $m$ $(1 \leq n, \ m \leq 1000)$.
- $m$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên $x_i$ $(0 \leq x_i \leq 1)$.
#### Output
- Một dòng duy nhất là số đảo có trong bảng.
#### Ví dụ
##### Input

4 5
0 1 0 1 
1 1 0 0
0 0 1 0
0 1 0 1
0 1 1 0

##### Output

5

:::spoiler **Ý tưởng**
- Ta sẽ chạy `DFS` trên những ô có giá trị `1` chưa được đi qua bao giờ với hàm `dfs(i, j)` sẽ dừng khi mà tất cả 4 ô xung quanh ô `(i, j)` đếu không phải là giá trị `1`. Đồng thời khi gặp 1 ô giá trị `1` chưa đi qua thì ta sẽ đẩy giá trị của kết quả cuối cùng lên 1.
- Trong mỗi lần `dfs` thì ta sẽ đánh dấu các ô giá trị `1` thành giá trị `0` để sau này khi duyệt tới các ô giá trị `1` mà đã đi qua thì chương trình sẽ bỏ qua.
:::
:::spoiler **Code**

#include <iostream>
#include <vector>
using namespace std;

int n, m, grid[1001][1001];

void dfs(int i, int j) {
    if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) return;

    grid[i][j] = 0; // đánh dấu đã thăm

    dfs(i + 1, j);
    dfs(i - 1, j);
    dfs(i, j + 1);
    dfs(i, j - 1);
}

int main() {
    int cnt = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1){
                dfs(i, j);
                cnt++;
            }
        }
    
    cout << cnt;
    return 0;
}

:::
### Bài 2: Tìm đường đi ngắn nhất trong mê cung
Cho một bảng `m x n` gồm `1` (ô bị chặn) và `0` (ô có thể đi được). Tìm số bước ít nhất đi từ `(0, 0)` đến `(m - 1, n - 1)` theo 4 hướng. Nếu không thể đi, in `-1`.
#### Input
- Dòng đầu tiên chứa hai số nguyên $n$ và $m$ $(1 \leq n, \ m \leq 1000)$.
- $m$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên $x_i$ $(0 \leq x_i \leq 1)$.
#### Output
- 1 dòng in ra số bước nhỏ nhất để đi từ `(0, 0)` tới `(m - 1, n - 1)`.
#### Ví dụ
##### Input

4 5
0 0 0 1 
1 1 0 0
0 1 0 1
0 1 0 0
0 1 1 0

##### Output

7

:::spoiler **Ý tưởng**
- Chạy thuật toán `BFS` bắt đầu từ ô `(0, 0)`, khi đẩy vào hàng đợi thì sẽ là để giá trị khoảng cách từ ô gốc tới ô đang xét và cặp vị trí của ô đang xét.
- Quá trình `BFS` sẽ dừng lại khi mà ta đến tới được ô đích `(m - 1, n - 1)` và in ra giá trị khoảng cách để tới ô đó. Còn nếu không, ta sẽ in ra `-1`.
:::
:::spoiler **Code**

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node {
    int x, y, steps;
};

int n, m, grid[1001][1001];

void shortestPath() {
    if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
        cout << -1;
        return;
    }
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    queue<Node> q;
    q.push({0, 0, 0});
    visited[0][0] = true;

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

    while (!q.empty()) {
        Node cur = q.front(); q.pop();

        if (cur.x == m - 1 && cur.y == n - 1) {
            cout << cur.steps;
            return;
        }

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

            if (nx >= 0 && ny >= 0 && nx < m && ny < n && 
                grid[nx][ny] == 0 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny, cur.steps + 1});
            }
        }
    }
    cout << -1; // không có đường đi
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++)
            cin >> grid[i][j];

    shortestPath();   

    return 0;
}

:::