---
title
Loang trên lưới (BFS/DFS) - Bài tập và lời giải
---

Loang trên lưới (BFS/DFS) - Bài tập và lời giải
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Bài tập vận dụng
## Bài 1: [CSES - Counting Rooms](https://cses.fi/problemset/task/1192)
### Đề bài
Cho bản đồ của một tòa nhà là một ma trận kích thước $n * m$. Mỗi ô có thể là sàn (kí hiệu là '**.**') hoặc tường (kí hiệu là '**#**'). Bạn có thể đi lên, đi xuống, sang trái, sang phải trên các ô sàn. Hãy đếm số phòng của tòa nhà.
#### Input:
* Dòng đầu tiên gồm hai số $n$, $m$: chiều cao và chiều rộng của tòa nhà ($1 \le n, m \le 1000$)
* $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự mô tả bản đồ. Mỗi ký tự có thể là '**.**' (sàn) hoặc '**#**' (tường)
#### Output:
* Ghi một số duy nhất là số phòng
#### Sample Input:

5 8
########
#..#...#
####.#.#
#..#...#
########

#### Sample Output:

3

### Lời giải
:::spoiler **Xem lời giải**
**Định nghĩa miền liên thông:** tập hợp nhiều nhất các ô trên bảng, sao cho tồn tại ít nhất một đường đi giữa hai ô bất kì trong tập hợp.

Từ định nghĩa trên, ta nhận thấy mỗi một phòng là một miền liên thông do luôn tồn tại đường đi từ ô sàn này đến ô sàn kia trong phòng. **$\Rightarrow$ Đây là một bài toán đếm miền liên thông trên bảng**.

Để tiến hành đếm miền liên thông, ta duyệt qua từng ô của bảng, nếu một ô $(x, y)$ chưa thuộc miền liên thông nào (chưa đến thăm) thì loang (DFS hoặc BFS) tìm miền liên thông có chứa ô đó (tìm các ô có thể đi qua được từ ô $(x, y)$) $\Rightarrow$ Tìm thấy một miền liên thông mới $\Rightarrow$ Tăng biến đếm.
:::

:::spoiler **Xem code mẫu**

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

const int moveX[] = {-1, 1, 0, 0};
const int moveY[] = {0, 0, -1, 1};

char a[1005][1005];
int n, m;
 
void dfs(int i, int j) {
    a[i][j] = '#';
    for (int k = 0; k < 4; k++) {
        int x = i + moveX[k];
        int y = j + moveY[k];
        if (1 <= x && x <= n && 1 <= y && y <= m && a[x][y] == '.') dfs(x, y);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '.') {
                dfs(i, j);
                ++ans;
            }
        }
    }
    cout << ans;
    return 0;
}

:::

## Bài 2: [VNOJ - Bảo vệ nông trang](https://oj.vnoi.info/problem/nkguard)
### Đề bài
Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này.

Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt một người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm $N$ $(1 < N \le 700)$ hàng và $M$ $(1 < M \le 700)$ cột. Mỗi phần tử của ma trận là độ cao $H_{ij}$ so với mặt nước biển $(0 \le H_{ij} \le 10000)$ của ô $(i, j)$. Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là một hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ $x$ không quá $1$ và chênh lệch tọa độ $y$ không quá $1$.
#### Input:
* Dòng $1$: Hai số nguyên cách nhau bởi dấu cách: $N$ và $M$
* Dòng $2 ...N + 1$: Dòng $i+1$ mô tả hàng $i$ của ma trận với $M$ số nguyên cách nhau bởi dấu cách: $H_{ij}$
#### Output:
* Một số nguyên duy nhất là số lượng đỉnh đồi
#### Sample Input:

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

#### Sample Output:

3

### Lời giải
:::spoiler **Xem lời giải**
Tương tự như bài 1, ta vẫn sẽ ứng dụng dfs vào bài này. Tuy nhiên, mảng `moveX` và `moveY` của chúng ta sẽ phải tăng lên 8 ô cần di chuyển bởi vì theo đề yêu cầu là 8 ô xung quanh ô $(i, j)$.

Theo như đề bài yêu cầu, thì đỉnh đồi là các đỉnh có **cùng độ cao** và **giới hạn bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn**, vậy nên ta cần phải kiểm tra xem liệu ô tiếp theo ta thăm có cùng độ cao và nằm trong bản đồ hay không? Tiếp theo sau khi đã loang hết ta cần lưu một biến $ok$ để check xem liệu xung quanh đỉnh mà ta vừa thăm có ô nào lớn hơn các ô trong đỉnh hay không? Nếu không có thì ta tỉnh đó là 1 đỉnh đồi.
:::

:::spoiler **Xem code mẫu**

#include <bits/stdc++.h>

using namespace std;

const int moveX[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int moveY[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int n, m;
int a[1001][1001];
bool visited[1001][1001];
bool ok;

void dfs(int i, int j) {
    visited[i][j] = 1;
    for (int k = 0; k < 8; k++) {
        int x = i + moveX[k];
        int y = j + moveY[k];
        if (1 <= x && x <= n && 1 <= y && y <= m) {
            if (a[i][j] < a[x][y]) ok = 0;
            if (!visited[x][y] && a[i][j] == a[x][y]) dfs(x, y);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!visited[i][j]) {
                ok = 1;
                dfs(i, j);
                if (ok) ++ans;
            }
        }
    }
    cout << ans;
    return 0;
}

:::

## Bài 3: [VNOJ - Gặm cỏ](https://oj.vnoi.info/problem/vmunch)

### Đề bài

Bessie rất yêu bãi cỏ của mình và thích thú chạy về chuồng bò vào giờ vắt sữa buổi tối.

Bessie đã chia đồng cỏ của mình là $1$ vùng hình chữ nhật thành các ô vuông nhỏ với $R \space (1 \le R \le 100)$ hàng và $C \space (1 \le C \le 100)$ cột, đồng thời đánh dấu chỗ nào là cỏ và chỗ nào là đá. Bessie đứng ở vị trí $R_b, C_b$ và muốn ăn cỏ theo cách của mình, từng ô vuông một và trở về chuồng ở ô $1, 1$; bên cạnh đó đường đi này phải là ngắn nhất.

Bessie có thể đi từ $1$ ô vuông sang $4$ ô vuông khác kề cạnh nhưng không được đi vào ô có đá hay đi ra khỏi đồng cỏ.

Dưới đây là một bản đồ ví dụ [với đá (' * '), cỏ (' . '), chuồng bò ('$B$'), và Bessie ('$C$') ở hàng $5$, cột $6$] và một bản đồ cho biết hành trình tối ưu của Bessie, đường đi được dánh dấu bằng chữ 'm'.

           Bản đồ               Đường đi tối ưu
        1 2 3 4 5 6  <-cột      1 2 3 4 5 6  <-cột
      1 B . . . * .           1 B m m m * .
      2 . . * . . .           2 . . * m m m
      3 . * * . * .           3 . * * . * m
      4 . . * * * .           4 . . * * * m
      5 * . . * . C           5 * . . * . m

Bessie ăn được $9$ ô cỏ.

Cho bản đồ, hãy tính xem có bao nhiêu ô cỏ mà Bessie sẽ ăn được trên con đường ngắn nhất trở về chuồng (tất nhiên trong chuồng không có cỏ đâu nên đừng có tính nhé)

#### Input
- Dòng $1$: $2$ số nguyên cách nhau bởi dấu cách: $R$ và $C$
- Dòng $2$ ... $R + 1$: Dòng $i + 1$ mô tả dòng $i$ với $C$ ký tự (và không có dấu cách) như đã nói ở trên.

#### Output
- Dòng $1$: Một số nguyên là số ô cỏ mà Bessie ăn được trên hành trình ngắn nhất trở về chuồng.

#### Sample input

5 6
B...*.
..*...
.**.*.
..***.
*..*.C

#### Sample output

9

### Lời giải
:::spoiler **Xem lời giải**
Bài toán yêu cầu tìm đường đi ngắn nhất giữa 2 điểm trên bảng. Do đó, ta dùng thuật toán loang theo chiều rộng (BFS) để loang tìm đường đi, và dùng một mảng phụ lưu khoảng cách ngắn nhất từ một ô bất kì đến ô bắt đầu duyệt (ô bắt đầu duyệt có thể là ô chuồng hoặc là ô có bò).
:::

:::spoiler **Xem code mẫu**

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

char a[105][105];
int d[105][105];
bool vis[105][105];
int moveX[] = {-1, 0, 0, 1};
int moveY[] = {0, -1, 1, 0};

int n, m;
pii s, t;

void bfs() {
    queue<pii> q;
    d[s.fi][s.se] = 0;
    vis[s.fi][s.se] = 1;
    q.push(s);
    while (!q.empty()) {
        int x = q.front().fi, y = q.front().se; 
        q.pop();
        for (int i = 0; i < 4; i++) {
            int u = x + moveX[i];
            int v = y + moveY[i];
            if (1 <= u && u <= n && 1 <= v && v <= m && !vis[u][v] && a[u][v] != '*') {
                d[u][v] = d[x][y] + 1;
                q.push({u, v});
                if (a[u][v] == 'C') return;
                vis[u][v] = 1;
            }
        }
    }
}

int main() {
    fastIO
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        cin >> a[i][j];
        if (a[i][j] == 'B') s = {i, j};
        if (a[i][j] == 'C') t = {i, j};
    }
    bfs();
    cout << d[t.fi][t.se];
    return 0;
}

:::