---
title: DFS / BFS
---
DFS/ BFS trên bảng
===

-----

###### ✍️ Author: 2School Guideline
###### 📋 Content:

[TOC]

-----
# Lời mở đầu
**DFS** và **BFS** đều là 2 thuật toán duyệt hoặc tìm kiếm trong ma trận. Tuy nhiên, **DFS** là thuật toán tìm kiếm **theo chiều sâu**, trong khi **BFS** lại tìm kiếm **theo chiều rộng**.
**DFS** và **BFS** có thể được sử dụng để giải quyết nhiều bài toán khác nhau trong lập trình, chẳng hạn như tìm đường đi trong một ma trận hoặc kiểm tra tính liên thông của một ma trận.
Ở trong bài viết này, tụi mình sẽ giới thiệu cho các bạn về ý tưởng, cách hoạt động cũng như ứng dụng của 2 thuật toán này trong lập trình thi đấu (trong bài viết này tụi mình chỉ dạy riêng mỗi DFS và BFS trên ma trận).
# Tìm kiếm theo chiều sâu (Depth First Search)
## Ý tưởng
Ý tưởng chung: với mỗi ô $(x, y)$, đi hướng đầu tiên tìm thấy. Khi không còn hướng để đi, quay ngược lại con đường đã đi và tìm hướng đi khác chưa được đi để đi.
Thuật toán **DFS** lập lại các thao tác sau cho đến khi đã duyệt qua hết tất cả các ô của ma trận:
- Tại một ô $(x, y)$ nếu như:
- Có ô $(u, v)$ có thể đi qua được từ ô $(x, y)$ chưa được thăm: đi đến ô $(u, v)$ và đánh dấu $(u, v)$ đã thăm.
- Không có ô nào có thể đến được từ ô $(x, y)$ chưa được thăm: quay lui lại ô trước đó và tìm các ô chưa được thăm.
## Cài đặt
Cài đặt **DFS** trên bảng có kích thước $n \cdot m$ có gốc là ô $(x, y)$.

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

const int N = 1e3;

int n, m, x, y;
int dr[4] = {0, -1, 0, 1}, dc[4] = {-1, 0, 1, 0}; ///mảng hằng giúp tìm ô kề nhanh
bool vis[N+1][N+1] = {false}; ///mảng đánh dấu ô đã đi qua để không đi lại các ô này

bool valid(int x, int y){ ///kiểm tra xem ô đi đến có nằm trong bảng không
    return (1 <= x && x <= n && 1 <= y && y <= m);
}

void DFS(int x, int y){ ///DFS từ ô (x, y)
    vis[x][y] = true; ///đánh dấu ô (x, y) đã đi qua
    for(int i = 0; i < 4; ++i){ ///duyệt các ô kề
        int nxt_x = x + dr[i], nxt_y = y + dc[i]; ///(nxt_x, nxt_y) là ô kề với ô (x, y)
        if(valid(nxt_x, nxt_y) && vis[nxt_x][nxt_y] == false){ ///nếu (nxt_x, nxt_y) nằm trong bảng và chưa được đi qua thì mình duyệt từ ô này
            DFS(nxt_x, nxt_y);
        }
    }
}

int main(){

    cin >> n >> m;
    cin >> x >> y;
    DFS(x, y);

    return 0;
}

- *Lưu ý : Code mẫu ở trên dành cho trường hợp có thể đi qua các ô kề cạnh.*
## Bài toán ví dụ
### Đề bài
- Cho ma trận $a$ có kích thước $n \cdot m$, tại mỗi ô $(x, y)$ của ma trận có $2$ trạng thái:
- Trạng thái $1$: $a[x][y] = 0$, tại ô này không có chướng ngại vật và có thể đến ô này.
- Trạng thái $2$: $a[x][y] = 1$, tại ô này có chướng ngại vật và không thể bước đến ô này.
- Bạn *Cánh Cụt* đang tham gia cuộc thi lập trình robot và thắc mắc rằng liệu robot *Pem* của bạn ấy có thể di chuyển đến ô $(X,Y)$ từ ô $(x,y)$ không? Biết rằng, tại mỗi ô $(i,j)$ bất kỳ, robot *Pem* chỉ có thể di chuyển đến các ô $(j + 1, j)$, $(i - 1, j)$, $(i, j - 1)$, $(i, j + 1)$.
- **Input**:
- Dòng đầu chứa $6$ số nguyên $n,$ $m,$ $x,$ $y,$ $X,$ $Y$
- Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa $m$ chữ số, lần lượt là $a[i][1], a[i][2], ... a[i][m]$.
- **Output**:
- Duy nhất một dòng, nếu robot *Pem* đi được thì xuất ra "YES", ngược lại thì "NO".
- **Giới hạn**:
- $n, m ≤ 10^3$,
- $x$, $X$ $≤ n$
- $y$, $Y$ $≤ m$
- $a[i][j]$ $≤ 1$
- **Ví dụ**:
- **Test ví dụ 1:**
- **Input**
- $5$ $5$ $1$ $2$ $5$ $5$
$1$ $0$ $0$ $0$ $1$
$0$ $1$ $1$ $1$ $0$
$1$ $0$ $0$ $1$ $1$
$1$ $1$ $0$ $0$ $1$
$1$ $1$ $1$ $0$ $0$
- **Ouput**
- NO
- **Test ví dụ 2:**
- **Input**
- $5$ $5$ $1$ $2$ $5$ $5$
$1$ $0$ $0$ $0$ $1$
$0$ $1$ $0$ $1$ $0$
$1$ $0$ $0$ $1$ $1$
$1$ $1$ $0$ $0$ $1$
$1$ $1$ $1$ $0$ $0$
- **Ouput**
- YES
### Code tham khảo

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

const int N = 1e3;

int n, m, x, y, X, Y;
int a[N+1][N+1];
int dr[4] = {0, -1, 0, 1}, dc[4] = {-1, 0, 1, 0};
bool found = false;
bool vis[N+1][N+1];

bool valid(int x, int y){
    return (1 <= x && x <= n && 1 <= y && y <= m);
}

void DFS(int x, int y){
    if(x == X && y == Y) found = true;
    if(found == true) return;
    vis[x][y] = true;
    for(int i = 0; i < 4; ++i){
        int nxt_x = x + dr[i], nxt_y = y + dc[i];
        if(valid(nxt_x, nxt_y) && vis[nxt_x][nxt_y] == false && a[nxt_x][nxt_y] == 0){
            DFS(nxt_x, nxt_y);
        }
    }
}

int main(){

    cin >> n >> m >> x >> y >> X >> Y;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> a[i][j];
        }
    }

    DFS(x, y);

    if(found) cout << "YES";
    else cout << "NO";

    return 0;
}

## Ứng dụng
- Tìm hoặc đếm miền liên thông trên bảng.
- Tìm đường đi giữa 2 điểm trên ma trận.

---
# Tìm kiếm theo chiều rộng (Breadth First Search)

## Ý tưởng

Có thể hiểu thuật toán như một ngọn lửa lan rộng trên ma trận:

- Ở bước thứ $0$, chỉ có ô gốc là $v[i][j]$ đang cháy.
- Ở mỗi bước tiếp theo, ngọn lửa đang cháy ở mỗi ô lại lan sang tất cả các ô có thể đến được, hay sau mỗi lần lặp của thuật toán, "vòng lửa" lại lan rộng ra theo chiều rộng.

## Thuật toán

Thuật toán tìm kiếm theo chiều rộng sử dụng một danh sách để chứa những đỉnh đang “chờ” thăm. Tại mỗi bước, ta thăm một ô trong danh sách, loại nó ra khỏi danh sách và cho những ô kề với nó chưa được thăm vào cuối danh sách. Thuật toán sẽ kết thúc khi danh sách rỗng.

Chính xác hơn, thuật toán có thể được mô tả như sau:

- Bước 1: Khởi tạo một hàng đợi $Q$ và một tập hợp $V$ để lưu trữ các ô đã duyệt.
- Bước 2: Bắt đầu tại một ô $v[i][j]$ (tùy vào đề bài), đưa ô đó vào $Q$ và $S$.
- Bước 3: Lặp lại cho đến khi $Q$ rỗng:
- Lấy ra một ô $v[a][b]$ từ $Q$.
- Duyệt qua tất cả các đỉnh $v[a_i][b_i]$ kề với $v[a][b]$ trong ma trận:
- Nếu $v_i$ chưa có trong $S$, tức là chưa được duyệt, thì đưa $w$ vào $Q$ và $S$.
- Bước 5: Kết thúc thuật toán.

**Mô phỏng thứ tự BFS:**


## Cài đặt
Tham khảo:
- [Áp Dụng Thuật Toán DFS, BFS Trên Lưới Ô Vuông](https://www.youtube.com/watch?v=CWZtxkPtCro)

**Cấu trúc dữ liệu:**

- Biến ``MaxN`` - Kích thước mảng.
- Mảng ``dx[]`` và ``dy[]`` - Mảng lưu lại dộ dịch ở mỗi ô.
- Mảng ``d[][]`` - Khoảng cách từ ô gốc tới ô đang xét.
- Mảng ``visit[][]`` - Mảng đánh dấu các đỉnh đã thăm.
- Mảng ``a[m][n]`` - Ma trận có m hàng và n cột.
- Mảng pair ``pre[x][y]`` - Vị trí của ô dẫn mình đến ô $(x, y)$
- Hàng đợi ``q`` - Chứa các đỉnh sẽ được duyệt theo thứ tự ưu tiên chiều rộng.

**Code:**

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

const int N = 1 + 1e3;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int n, m;
int a[N][N];
int visit[N][N], d[N][N];
pair <int, int> pre[N][N];
vector<pair<int, int>> ans;

bool valid(int x, int y){
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

void bfs(int x, int y){
    int res = 0;
    queue<pair<int, int>> q;
    q.push({x, y}); // Đưa ô x,y vào hàng đợi.
    visit[x][y] = 1; // Đánh dấu đã đi qua.
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        res++;
        for(int i = 0 ; i < 4 ; ++i){
            int i1 = x + dx[i];
            int j1 = y + dy[i];
            if(valid(i1, j1) && a[i1][j1] == 0 && !visit[i1][j1]){
                q.push({i1, j1});
                d[i1][j1] = d[x][y]+1;
                visit[i1][j1] = 1;
                pre[i1][j1] = {x, y};
            }
        }
    }
}

int main(){
    int x, y; cin >> x >> y;
    bfs(x, y);
    return 0;
}

**Truy vết**

Cài đặt truy vết đường đi từ ô nguồn $v[x][y]$ đến ô $v[u][v]$:

void trace(int u, int v){
    if (!visit[u][v]) cout << "No path!";
    else {
        vector<pair<int,int>> path;
        while(!(u == 0 && v == 0)){
            path.push_back({u, v});
            int u = u, v = v;
            u = pre[u][v].first, v = pre[u][v].second;
        }
        reverse(path.begin(), path.end());

        cout << "Path:\n";
        for (auto v : path) cout << v.first << ' ' << v.second << '\n';
    }
}

## Ứng dụng
Thuật toán BFS có nhiều ứng dụng trong lý thuyết ma trận và thực tế. Một số ứng dụng phổ biến của BFS là:

- **Tìm kiếm đường đi ngắn nhất** giữa hai ô trong một ma trận. BFS sẽ duyệt qua các ô theo thứ tự từng lớp và đảm bảo rằng đường đi ngắn nhất sẽ được tìm thấy đầu tiên. (Tham khảo: [SERGRID - Grid](https://www.spoj.com/problems/SERGRID/))
- **Tìm kiếm các thành phần liên thông** của một của một ma trận. (Tham khảo: [VBGRASS - Bãi cỏ ngon nhất](https://vn.spoj.com/problems/VBGRASS/))

________________

### Tìm đường đi ngắn nhất bằng BFS:
Đề bài: [SERGRID - Grid](https://www.spoj.com/problems/SERGRID/)
Tham khảo: [Thuật toán bài SERGRID - Grid](https://thuattoan.phamvanlam.com/spoj-com-thuat-toan-bai-sergrid-grid/)

**Đề bài:**

Bạn đang ở trên một cái lưới $N * M$ nơi mà mỗi ô vuông trên lưới đó có một số trên đó. Từ một ô cho trước trên lưới có một số có giá trị $k$. Một lần di chuyển bao gồm chính xác k ô vuông theo 4 hướng chính. Biết bạn không thể nhảy ra khỏi lưới. Hỏi số bước nhỏ nhất để di chuyển từ ô vuông trên cùng bên trái đến ô vuông dưới cùng bên phải là bao nhiêu.

**Đầu vào:**
- Dòng đầu tiên của đầu vào bao gồm 2 số nguyên $N$ và $M$ $(1 <= N, M <= 500)$, biểu thị kích thước của lưới. Đảm bảo rằng ít nhất một cạnh của lưới (tức $N$ hoặc $M$) sẽ lớn hơn $1$.
- $N$ dòng tiếp theo, mỗi dòng chứa $M$ chữ số và không có dấu cách, biểu thị ma trận $N * M$. Mỗi chữ số có giá trị từ 0 đến 9 (bao gồm cả 2 chữ số đó).

**Đầu ra:**
- In ra duy nhất trên $1$ dòng một số - biểu diễn giá trị là số bước nhỏ nhất để di chuyển từ góc trên cùng bên trái xuống góc dưới cùng bên phải. Nếu không thì in ra $-1$.

**Ví dụ:**

**Giải**:

Đây là bài toán cơ bản áp dụng thuật toán tìm kiếm theo chiều rộng BFS. Mình sẽ bắt đầu từ điểm đầu tiên là điểm trên cùng bên trái.

**Code:**

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 1 + 1e3;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int n, m;
int a[MaxN][MaxN], visit[MaxN][MaxN], d[MaxN][MaxN];

void bfs(int x, int y) {
  int res = 0;
  queue<pair<int, int>> q;
  q.push({x, y});   // Đưa ô x,y vào hàng đợi.
  visit[x][y] = 1;  // Đánh dấu đã đi qua.
  while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    if (!a[x][y]) continue;
    res++;
    for (int i = 0; i < 4; ++i) {
      int i1 = x + dx[i] * a[x][y];
      int j1 = y + dy[i] * a[x][y];
      if (i1 >= 0 && i1 < n && j1 >= 0 && j1 < m && !visit[i1][j1]) {
        q.push({i1, j1});
        d[i1][j1] = d[x][y] + 1;
        visit[i1][j1] = 1;
      }
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    char tmp[MaxN];
    cin >> tmp;
    for (int j = 0; j < m; j++) {
      a[i][j] = tmp[j] - '0';
      visit[i][j] = 0;
      d[i][j] = 0;
    }
  }

  bfs(0, 0);
  // Nếu giá trị ô cuối cùng vẫn bằng 0, nghĩa là nó được thăm
  if (visit[n - 1][m - 1] == 0)
    cout << -1 << endl;
  else
    cout << d[n - 1][m - 1] << endl;
  return 0;
}

**Độ phức tạp:** $O(M \times N)$
_________________________________

### Tìm thành phần liên thông bằng BFS:
Tham khảo: [Thuật toán Loang](https://howkteam.vn/course/cau-truc-du-lieu-va-giai-thuat/thuat-toan-loang-4388)

**Đề bài:**

Một vùng biển được chia ra thành một lưới ô vuông có kích thước $N * M$. Một tai nạn xảy ra khiến cho dầu bị tràn ra biển. Các ô có dầu tràn được kí hiệu bằng số $1$, các ô không có dầu tràn được kí hiệu bằng số $0$. Một vết loang là một tập hợp các ô chung cạnh được kí hiệu bằng số $1$.

Hãy đếm số lượng vết dầu loang và in ra kích thước của từng vết dầu theo thứ tự từ nhỏ đến lớn.

**Đầu vào:**
- Dòng đầu tiên chứa $2$ số nguyên dương $N, M$ lần lượt thể hiện cho số hàng và số cột của lưới ô vuông tượng trưng cho vùng biển $(N, M \leq 10^{3})$
- $N+1$ dòng tiếp theo biểu thị Ma trận kích thước $N \times M$ trong đó các ô có dầu có giá trị là $1$, các ô còn lại có giá trị là $0$.

**Đầu ra:**
- Dòng đầu tiên chứa số nguyên duy nhất là số lượng vết dầu loang.
- Dòng thứ hai là kích thước của các vết dầu được sắp xếp từ nhỏ đến lớn.

**Ví dụ:**

Đây là hình ảnh minh hoạ cho ma trận trên với các vết dầu được tô màu.


**Giải:**

Từ một ô mang giá trị $1$, ta sẽ xem liệu có ô nào chung cạnh mang giá trị $1$ không. Nếu có, ta sẽ tiếp tục quá trình trên đến khi nào chạm phải một ô mang giá trị $0$. Khi đó, tập các ô mang giá trị $1$ mà ta vừa đi qua sẽ tạo thành một vết dầu.

Cách làm này giống như việc ta đổ nước ra sàn, nước sẽ chảy ra mọi phía và chỉ ngừng chảy khi chạm phải vật cản. Khi đó, những khu vực nước chảy qua sẽ bị đọng nước. Chính vì sự tương tự này mà ta gọi thuật toán là Loang.

**Code:**

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 1 + 1e3;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int n, m;
int a[MaxN][MaxN], visit[MaxN][MaxN], d[MaxN][MaxN];

vector<int> ans;

int bfs(int x, int y){
    int res = 0;
    queue<pair<int, int>> q;
    q.push({x, y}); // Đưa ô x,y vào hàng đợi.
    visit[x][y] = 1; // Đánh dấu đã đi qua.
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        res++;
        for(int i = 0 ; i < 4 ; ++i){
            int i1 = x + dx[i];
            int j1 = y + dy[i];
            if(i1 > 0 && i1 <= n && j1 > 0 && j1 <= m && a[i1][j1] == 1 && !visit[i1][j1]){
                q.push({i1, j1});
                visit[i1][j1] = 1;
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j) 
            cin >> a[i][j];
    
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(a[i][j] == 1 && !visit[i][j]) ans.push_back(bfs(i, j));
    
    cout << ans.size() << endl;
    
    sort(ans.begin(), ans.end());
    for(int i : ans) 
        cout << i << " ";

    return 0;
}

**Độ phức tạp:** $O(M \times N)$

# **Bài tập**
**Bài 1 (Counting Rooms):** https://cses.fi/problemset/task/1192
**Đề bài (đã dịch):**
Cho một bảng có kích thước là $n$ x $m$ ô vuông, mỗi ô vuông có 2 trạng thái gồm: "." hoặc "#". Bạn có thể đi bộ trái, phải, lên và xuống qua các ô vuông ".".
**Input:**
Dòng đầu tiên chứa hai số nguyên $n$ và $m$: chiều dài và chiều rộng của bản đồ.
Sau đó có $n$ dòng mỗi dòng chứa $m$ ký tự mô tả bảng. Mỗi ký tự đại diện cho đi được hoặc không đi được, tương ứng với dấu . hoặc #. Ký hiệu $A$ và $B$ tương ứng với vị trí bắt đầu và kết thúc.
**Output:**
In ra một số nguyên duy nhất: số phòng tìm được(các phòng được tách với nhau nếu không đi được từ phòng này sang phòng khác).
**Ví dụ:**
**Input:**

5 8
########
#.A#...#
#.##.#B#
#......#
########

**Output:**

YES
9
LDDRRRRRU

**Bài 2 (Labyrinth):** https://cses.fi/problemset/task/1193
**Đề bài (đã dịch):**
Cho một bản đồ mê cung, tìm một đường đi từ đầu đến cuối. Bạn có thể đi qua trái, phải, lên và xuống (mỗi lần $1$ bước).
**Input:**
Dòng đầu tiên chứa hai số nguyên $n$ và $m$: chiều cao và chiều rộng của bản đồ.

Sau đó có $n$ dòng, mỗi dòng chứa $m$ ký tự mô tả mê cung. Mỗi ký tự đại diện cho ô đi qua được (ký hiệu `.`), ô không đi qua được (ký hiệu `#`), điểm bắt đầu (ký hiệu $A$) hoặc điểm kết thúc (ký hiệu $B$). Đầu vào chỉ có duy nhất một điểm $A$ và một điểm $B$.
**Output:**
In ra `YES` nếu có một con đường đi từ $A$ đến $B$ và in ra `NO` nếu không có.

Nếu có đường đi thì in ra độ dài của đường đi ngắn nhất và mô tả con đường đó dưới dạng một xâu các ký tự $L$ (trái), $R$ (phải), $U$ (lên) và $D$ (xuống). Bạn có thể in bất kỳ đường đi nào hợp lệ.

**Ràng buộc**
$1 \le n, m \le 1000$

**Ví dụ**
**Input**

5 8
########
#.A#...#
#.##.#B#
#......#
########

**Output**

YES
9
LDDRRRRRU

**Bài 3 (Monsters):** https://cses.fi/problemset/task/1194
**Đề bài (đã dịch):**
Cho một bảng có kích thước $n$ x $m$, cho vị trí của bạn và các quái vật. Khi bạn di chuyển $1$ bước, quái vật cũng có thể di chuyển một bước. Nhiệm vụ bạn là đi đến các ô ở đường biên mà không gặp bất cứ con quái vật nào.

In ra một lộ trình mà bạn có thể đi. Biết rằng quái vật sẽ thực hiện thao tác di chuyển tốt nhất.
**Input:**
Dòng đầu tiên chứa hai số nguyên $n$ và $m$: chiều cao và chiều rộng của bản đồ.

Sau đó có $n$ dòng mỗi dòng chứa $m$ ký tự mô tả bảng. Mỗi ký tự đại diện cho ô đi qua được (ký hiệu **.**), ô không đi qua được (ký hiệu **#**), vị trí của bạn (ký hiệu $A$) hoặc vị trí của quái vật (ký hiệu $M$). Đầu vào chỉ có duy nhất một điểm có ký hiệu $A$.

**Output:**
In ra `YES` nếu có đường đi khả thi, và in ra `NO` nếu không.

Nếu tồn tại đường đi khả thi thì in ra một ví dụ về một đường đi hợp lệ (độ dài của đường đi và mô tả đường đi đó bằng các ký tự $L$ (trái), $R$ (phải), $U$ (lên) và $D$ (xuống). Bạn có thể in bất kỳ lộ trình nào, miễn là độ dài của nó không vượt quá $n$ x $m$ bước đi.

**Ràng buộc**
$1 \le n, m \le 1000$

**Ví dụ:**
**Input**

5 8
########
#M..A..#
#.#.M#.#
#M#..#..
#.######

**Output**

YES
5
RRDDR