- title Loang trên lưới (BFS/DFS) - Loang trên lưới (BFS/DFS) === - ###### ✍️ Author: 2School Guideline ###### 📋 Content: [TOC] - # Giới thiệu chung Thuật toán loang là một trong những thuật toán được ứng dụng khá nhiều trong công nghệ thông tin nói chung và lập trình thi đấu nói riêng. Nó được áp dụng điển hình vào các trò chơi nổi tiếng như dò mìn, line 98,... . Ngoài được áp dụng trên lưới ra, nó còn được áp dụng trên đồ thị. Thế nhưng trong giới hạn bài viết lần này, bọn mình chỉ giới thiệu cho mọi người về thuật toán loang trên lưới (ma trận). # Thuật toán loang Đúng như tên gọi của nó, thuật toán loang sử dụng nguyên lí vết dầu loang. Từ một vết dầu nhỏ sẽ được loang ra xung quanh. Tương tự như vậy, từ một ô trên ma trận, thuật toán sẽ loang ra xung quanh để giải quyết các bài toán. Như trong trò chơi dò mìn, để giải quyết được trò chơi, bạn phải chọn một điểm ban đầu, và xử lí các thông tin tại đó để dò được các vị trí bãi mìn xung quanh cho tới khi không dò được nữa.  Hay như khi tìm đường đi trên mê cung, thuật toán sẽ dò tất cả các đường đi xung quanh người chơi để tìm được lối ra cho đến khi không thể dò được nữa.  Tư tưởng của thuật toán loang chỉ có như vậy, chúng ta sẽ đi đến 2 cách tiếp cận chính của nó. # Tìm kiếm theo chiều sâu (DFS - Depth-first search) ## 1. Bài toán ### 1.1. Đặt vấn đề Ngày xửa ngày xưa, ở một vương quốc nọ, có một nàng công chúa vô cùng xinh đẹp. Tuy nhiên, trong một lần vào rừng dạo chơi, cô đã bị một mụ phù thủy già bắt cóc và nhốt vào một căn phòng kín trong lâu đài rộng lớn của mụ. Triều đình khi hay tin công chúa mất tích đã vô cùng hoảng hốt, nhưng giữa lúc ấy, có một chàng hoàng tử khôi ngô tuấn tú xung phong đi giải cứu công chúa. Nhờ sự giúp đỡ của các vị tiên rừng, vị hoàng tử đã tìm thấy lâu đài hắc ám của mụ phù thủy. Giả sử lâu đài được mô phỏng dưới dạng một ma trận 2 chiều (lưới/bảng) $m * n$, gồm các kí tự: - '**.**' - Phòng trống - '**#**' - Phòng có quái vật - '**A**' - Nơi hoàng tử đang đứng - '**B**' - Nơi công chúa bị giam giữ Đảm bảo chỉ có một ô chứa kí tự '**A**' và một ô chứa kí tự '**B**'. Hãy tìm một đường đi từ vị trí của hoàng tử đến vị trí của công chúa. Biết rằng, từ một ô, ta có thể đi tiếp qua các ô có chung cạnh với nó mà không có quái vật: từ ô có tọa độ $(x, y)$, bạn có thể đi qua các ô $(x + 1, y)$, $(x - 1, y)$, $(x, y + 1)$, $(x, y - 1)$ nếu các ô không được đánh dấu bằng kí tự '**#**'. Nếu không có đường đi, xuất ra "**IMPOSSIBLE**". Nếu tồn tại đường đi: - Xuất ra '**U**' nếu hoàng tử cần đi đến ô $(x - 1, y)$ từ ô $(x, y)$ - Xuất ra '**D**' nếu hoàng tử cần đi đến ô $(x + 1, y)$ từ ô $(x, y)$ - Xuất ra '**L**' nếu hoàng tử cần đi đến ô $(x, y - 1)$ từ ô $(x, y)$ - Xuất ra '**R**' nếu hoàng tử cần đi đến ô $(x, y + 1)$ từ ô $(x, y)$ Bạn chỉ cần xuất một đường đi hợp lệ. (Giới hạn ví dụ: $1 \le n, m \le 1000$) ### 1.2. Ý tưởng giải Ta triển khai ý tưởng giải bài toán: - Sử dụng một mảng đánh dấu, đánh dấu các ô đã đi qua, đảm bảo mỗi ô chỉ được đi qua đúng 1 lần. - Sử dụng một mảng truy vết đường đi: * Từ ô $(x, y)$ đi đến ô $(x - 1, y)$: lưu ký tự '**U**' * Từ ô $(x, y)$ đi đến ô $(x + 1, y)$: lưu ký tự '**D**' * Từ ô $(x, y)$ đi đến ô $(x, y - 1)$: lưu ký tự '**L**' * Từ ô $(x, y)$ đi đến ô $(x, y + 1)$: lưu ký tự '**R**' - Các bước thực hiện: * Từ ô xuất phát, khi tìm thấy một lối đi vào ô khác (ô thuộc phạm vi lâu đài, không có quái vật), nếu ô chưa được đi qua thì đi đến ô đó, đánh dấu ô đã đi qua và lặp lại bước này. * Nếu ô không còn lối đi nào khác (các ô kề không hợp lệ hoặc đã được đi qua hết) thì quay lui về ô trước đó và tìm lối đi khác. * Nếu đi qua ô chứa kí tự '**B**' $\Rightarrow$ tìm thấy công chúa $\Rightarrow$ kết thúc quá trình tìm kiếm và tiến hành xuất đường đi. * Nếu sau khi duyệt qua hết các đường có thể đi mà ô '**B**' chưa được đánh dấu là đã đi qua $\Rightarrow$ không có đường đi từ vị trí của hoàng tử đến chỗ công chúa $\Rightarrow$ xuất ra "**IMPOSSIBLE**" ### 1.3. Cài đặt mẫu ```cpp=

include using namespace std; int n, m, XA, YA, XB, YB; char a[1000][1000]; int r[4] = {0, 0, -1, 1}; int c[4] = {-1, 1, 0, 0}; string dr = "LRUD"; bool v[1000][1000]; bool f; string track; bool check(int x, int y) { if(x < 0) return 0; else if(x >= n) return 0; else if(y < 0) return 0; else if(y >= m) return 0; else if(a[x][y] == '#') return 0; return 1; } void dfs(int x, int y) { if(x == XB && y == YB) f = true; if(f == true) return; v[x][y] = true; for(int i = 0; i < 4; i) { int nx = x + r[i], ny = y + c[i]; if(check(nx, ny) && v[nx][ny] == false){ track.push_back(dr[i]); dfs(nx, ny); if(f == true) return; track.pop_back(); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i < n; i){ for(int j = 0; j < m; j++) cin >> a[i][j]; } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(a[i][j] == 'A'){ XA = i; YA = j; } else if(a[i][j] == 'B'){ XB = i; YB = j; } } } dfs(XA, YA); if(f == false) cout << "IMPOSSIBLE"; else cout << track; } ``` ## 2. Thuật toán Tìm kiếm theo chiều sâu - DFS Bài toán ví dụ vừa rồi là điển hình cho một vấn đề mà chúng ta sử dụng **DFS** để giải quyết. Ở phần này, ta cùng tổng quát hóa ý tưởng cũng như cách cài đặt của giải thuật này. ### 2.1. Ý tưởng **Ý tưởng chung:** Từ ô có tọa độ $(x, y)$, đi đến ô kề hợp lệ đầu tiên. Khi không thể đi được nữa, quay ngược lại ô trước đó và tìm các đường đi khác chưa được đi. Thuật toán **DFS** lặp lại các bước sau cho đến khi duyệt hết các ô có thể đi qua trong ma trận: - Tại một ô $(x, y)$: * Có ô $(x', y')$ hợp lệ, có thể đi qua được từ ô $(x, y)$ và chưa được thăm: đi đến ô $(x', y')$ và đánh dấu $(x', y')$ đã thăm. * Các ô có thể đi được từ ô $(x, y)$ đều đã được thăm hoặc không hợp lệ; đã xử lý xong các ô kề với $(x, y)$: quay lui lại ô trước đó và tìm các ô chưa được thăm. Sơ đồ khối mô tả thuật toán (hướng dẫn đọc sơ đồ khối xem tại [Phụ lục](

Phụ-lục)):  ### 2.2. Cài đặt ```cpp= void dfs(int x, int y) { v[x][y] = true; for(int i = 0; i < 4; ++i) { int nx = x + r[i], ny = y + c[i]; if(check(nx, ny) && v[nx][ny] == false) dfs(nx, ny); } } ``` ### 2.3. Ứng dụng Các ứng dụng phổ biến của thuật toán **Tìm kiếm theo chiều sâu (DFS)**: - Tìm hoặc đếm **miền liên thông** trên lưới (**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ìm **đường đi** giữa 2 ô trên lưới. # Tìm kiếm theo chiều rộng (BFS - Breadth-first search) ### 1. Đề bài Một tai nạn hàng hải đã khiến dầu tràn ra biển. Để có được thông tin về mức độ nghiêm trọng của thảm họa này, người ta phải phân tích các hình ảnh chụp từ vệ tinh, từ đó tính toán chi phí khắc phục cho phù hợp. Đối với điều này, số lượng vết dầu loang trên biển và kích thước của mỗi vết loang phải được xác định. Vết loang là một mảng dầu nổi trên mặt nước. Để tiện cho việc xử lí, hình ảnh được chuyển đổi thành một ma trận nhị phân kích thước $N×M \space (1≤N,M≤250)$. Với $1$ là ô bị nhiễm dầu, và $0$ là ô không bị nhiễm dầu. Vết dầu loang là tập hợp của một số ô bị nhiễm dầu có chung cạnh. Họ đã thuê bạn để giúp họ xử lí hình ảnh. Công việc của bạn là đếm số lượng vết loang trên biển và kích thước tương ứng của từng vết. ### 2. Ý tưởng Cố định một toạ độ $(i, j)$ là ô bị nhiễm dầu, ta sẽ loang ra các ô chung cạnh $(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)$ để đếm các ô bị nhiễm dầu xung quanh. Ta sẽ áp dụng **BFS** vào để giải bài toán trên. Tư tưởng chính của thuật toán: - Khác với **DFS**, thay vì cố gắng đi tới 1 cạnh cho tới khi không đi được nữa, thuật toán **BFS** sẽ đi qua tất cả các cạnh chung của ô $(i, j)$, sau đó lại lần lượt đi qua tất cả các cạnh chung của ô $(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)$, ... - Tóm lại, trong mỗi lần lặp của thuật toán, ô nào gần ô nguồn $(i, j)$ nhất sẽ được thăm trước.  ### 3. Cài đặt - Ta sẽ áp dụng hàng đợi vào cài đặt duyệt ưu tiên theo chiều rộng. - **Bước 1:** Khởi tạo - Ta sẽ đánh dấu ô $(i, j)$ (ô $1$) là ô được thăm đầu tiên. - Ban đầu hàng đợi $q$ sẽ chứa ô $(i, j)$ này. - Khởi tạo kích thước vết dầu là $1$ (ô $(i, j)$) - **Bước 2:** Lặp lại các bước cho tới khi hàng đợi rỗng - Ta sẽ lấy ô $(u, v)$ ở đầu hàng đợi ra và xoá ô này trong hàng đợi. - Xét tất cả các ô $(x, y)$ bị nhiễm dầu kề với $(u, v)$ nằm trong ma trận mà chưa được đánh dấu: - Đánh dấu ô $(x, y)$ đã được thăm. - Tăng kích thước của vết dầu lên $1$ đơn vị. - Đẩy ô $(x, y)$ vào hàng đợi. - **Bước 3:** Lúc này tất cả các vết dầu bị nhiễm xung quanh ô $(i, j)$ đã được thăm, ta trả ra kết quả và kết thúc thuật toán. :::spoiler **Code mẫu** ```cpp=

include using namespace std; const int moveX[] = {-1, 1, 0, 0}; const int moveY[] = {0, 0, -1, 1}; int n, m, a[255][255], vis[255][255]; int bfs(int i, int j) { queue< pair > q; int sizeSlick = 1; q.push({i, j}); vis[i][j] = 1; while (!q.empty()) { int u = q.front().first, v = q.front().second; q.pop(); for (int k = 0; k < 4; k++) { int x = u + moveX[k]; int y = v + moveY[k]; // Nếu ô (x, y) là một ô nhiễm dầu còn nằm trong lưới và chưa được thăm thì ta sẽ thăm if (1 <= x && x <= n && 1 <= y && y <= m && a[x][y] == 1 && vis[x][y] == 0) { vis[x][y] = 1; sizeSlick++; q.push({x, y}); } } } return sizeSlick; } 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]; } vector slicks; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // Nếu ô (i, j) bị nhiễm dầu và ô đó chưa được thăm thì ta sẽ tiến hành thăm if (a[i][j] == 1 && vis[i][j] == 0) { slicks.push_back(bfs(i, j)); } } } cout << slicks.size() << endl; for (auto slick: slicks) cout << slick << " "; return 0; } ``` ::: ### 4. Ứng dụng - Tất cả các ứng dụng của **DFS**. - Tìm đường đi ngắn nhất trong mê cung. (Ứng dụng này được rút ra từ ý tưởng chính của thuật toán là lan rộng ra các cạnh và ô nào gần $(i, j)$ hơn sẽ được thăm trước, từ đó đường đi gần hơn tới đích sẽ được thăm trước các đường đi khác.) # 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 ``` ## 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 ``` ## 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 ``` # Phụ lục Hướng dẫn xem sơ đồ khối:   Tham khảo tại: [Hướng dẫn vẽ và đọc sơ đồ khối](https://xaydungso.vn/bai-viet-khac/tim-hieu-quy-uoc-ve-so-do-khoi-cho-nguoi-moi-bat-dau-vi-cb.html) # Nguồn tham khảo [2SG - DFS/BFS](https://hackmd.io/@hda/r1pN4trM3/edit) [Competitive Programmer’s Handbook](https://cses.fi/book/book.pdf) [Hướng dẫn vẽ và đọc sơ đồ khối](https://xaydungso.vn/bai-viet-khac/tim-hieu-quy-uoc-ve-so-do-khoi-cho-nguoi-moi-bat-dau-vi-cb.html)