Thuật toán Loang

Dẫn nhập

Trong các bài học trước, chúng ta đã cùng nhau tìm hiểu về thuật toán duyệt đồ thị theo chiều rộng BFS. Hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một thuật toán được áp dụng khá phổ biến là Loang. Đây có thể coi là ứng dụng phổ biến nhất của thuật toán BFS.

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• Các kiến thức cần thiết để theo dõi khóa học
• Đồ thị và cây
• BFS và DFS
• Queue

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Thuật toán Loang

---

Bài toán đặt ra

Ta có một bài toán như sau:

Một vùng biển được chia ra thành một lưới ô vuông có kích thước . 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.

Input:

• Dòng 1: 2 số nguyên dương  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
• Dòng : Ma trận kích thước  trong đó các ô có dầu có giá trị là 1, các ô còn lại có giá trị là 0

Output:

• Dòng 1: Số nguyên duy nhất là số lượng vết dầu loang
• Dòng 2: Kích thước của các vết dầu được sắp xếp từ nhỏ đến lớn

Ví dụ:

Input	Output
4 5 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1	4 1 2 3 6

Giải thích 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.

---

Ý tưởng

Ý tưởng của bài toán thực ra khá đơn giản và đó cũng chính là cách chúng ta giải quyết bài này một cách thủ công: 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.

Vậy thì ta sẽ triển khai chi tiết ý tưởng trên như thế nào?

Ta nhận thấy rằng ta hoàn toàn có thể mô hình hoá được ma trận trên thành một đồ thị trong đó mỗi ô là một đỉnh, cứ hai ô có chung cạnh sẽ tạo thành một cạnh trên đồ thị của chúng ta. Khi này, ta sẽ duyệt đồ thị để tìm các thành phần liên thông chứa toàn số 1.

---

Cách cài đặt

Ta sẽ cần một mảng mark[][] để đánh dấu các ô đã được xét.

Thuật toán diễn ra như sau:

• Ta sẽ duyệt tất cả các ô trong ma trận, nếu như gặp một ô có giá trị 1 và chưa được đánh dấu (mark[][] = 0) thì ta sẽ loang từ ô đó
• Quá trình loang:
  • Ta sẽ có một hàng đợi chứa các ô mang giá trị 1 và đang chờ kiểm tra xem liệu có loang tiếp từ các ô đó được không. Ban đầu, hàng đợi chứa ô mang giá trị 1 mà ta gặp ở trên
  • Mỗi lần, ta sẽ lấy ra từ hàng đợi một ô
  • Ta sẽ kiểm tra xem các ô có chung cạnh nó có tồn tại ô nào mang giá trị 1 và chưa được đánh dấu không. Nếu có, ta sẽ thêm ô đó vào hàng đợi và đánh dấu đỉnh đó. Đây là một phần khá thú vị và mình sẽ trình bày riêng ở dưới
  • Quá trình kết thúc khi hàng đợi rỗng. Kích thước vết dầu chính là số phần tử đã từng được đẩy vào hàng đợi

Ở trong quá trình trên, thao tác tìm các ô chung cạnh thoả mãn sẽ là thao tác “khó nhằn” nhất. Ta thấy, ta sẽ quản lý các ô theo tọa độ của chúng. Do đó, ta sẽ lưu tâm đến quan hệ toạ độ của một ô với các ô chung cạnh của nó.

Xét ô vuông có toạ độ , ta thấy 4 ô vuông xung quanh nó sẽ có toạ độ như sau:

Lúc này, các bạn có thể nghĩ đơn giản là ta sẽ tạo ra 4 cặp biến tương ứng với tọa độ của 4 ô vuông xung quanh ô  để xét. Cách làm này không sai. Tuy nhiên, giả sử nếu sau này phát sinh những bài toán cần tìm quan hệ của nhiều hơn 4 ô xung quanh thì cách làm này sẽ khiến code vô cùng khó đọc. Vậy thì giải pháp là gì?

Ta thấy, toạ độ các ô vuông xung quanh ô  là toạ độ ô  và được thêm bớt một giá trị cố định. Do đó, ta sẽ lập 2 mảng hằng dx[]={0, 0, 1, -1} và dy[]={1, -1, 0, 0} thể hiện cho các giá trị được cộng thêm vào toạ độ  để được toạ độ các ô xung quanh. Khi này, chỉ cần dùng vòng lặp để duyệt qua 4 cặp giá trị ở hai mảng trên là ta sẽ có toạ độ 4 ô xung quanh.

Như vậy liệu đã hoàn thành chưa nhỉ? Theo các bạn, có yếu tố nào mà ta đã bỏ quên hay không? Các bạn hãy tạm ngưng bài học ở đây và code thử theo ý tưởng trên nhé. Đây coi như là một bài tập nhỏ cho các bạn. Hãy chạy thử chương trình các bạn code và kiểm tra xem ý tưởng trên còn gì thiếu sót không nhé!

Các bạn đã nhận ra ý tưởng trên còn bỏ sót yếu tố nào chưa? Hãy cùng theo dõi tiếp bài học nhé.

Ta thấy rằng, với các ô ở hàng trên cùng, sẽ không tồn tại các ô ở phía trên nó. Với các ô ở hàng cuối cùng, sẽ không tồn tại các ô ở dưới nó. Tương tự với các ô ở cạnh trái và cạnh phải cũng sẽ không tồn tại ô ở phía bên trái và bên phải nó. Do đó, khi xét các ô vuông có chung cạnh, ta sẽ cần kiểm tra xem ô vuông đó có nằm trong hình vuông đang được xét không. Điều kiện để kiểm tra ô vuông  có thuộc hình đang xét không đó là  && .

---

Code

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

typedef long long ll;

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

int n, m, a[MaxN][MaxN], mark[MaxN][MaxN];
vector<int> ans;

int Loang(int x, int y){
    int res = 0;
    queue<pair<int, int>> q;
    q.push({x, y});
    mark[x][y] = 1;
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();
        res++;
        for(int i = 0 ; i < 4 ; ++i)
        if(x + dx[i] > 0 && x + dx[i] <= n && y + dy[i] > 0 && y + dy[i] <= m && a[x + dx[i]][y + dy[i]] == 1 && !mark[x + dx[i]][y + dy[i]]){
            q.push({x + dx[i], y + dy[i]});
            mark[x + dx[i]][y + dy[i]] = 1;
        }
    }
    return res;
}

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    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 && !mark[i][j]) ans.push_back(Loang(i, j));
    cout << ans.size() << endl;
    sort(ans.begin(), ans.end());
    for(int i : ans) cout << i << " ";

    return 0;
}

---

Độ phức tạp

Thuật toán trên đơn thuần là duyệt qua tất cả các ô vuông nên độ phức tạp sẽ là .

---

Mở rộng

Thuật toán Loang chỉ là một trong những ứng dụng của thuật toán BFS trong lập trình. Ngoài ra, các bạn có thể tìm hiểu thêm về các ứng dụng sau của thuật toán BFS:

• Tìm đường đi ngắn nhất trong đồ thị không trọng số
• Tìm đường đi ngắn nhất trong đồ thị có trọng số 0 hoặc 1
• Tìm kiếm thành phần liên thông trong đồ thị (Thực chất chính là bài toán trên của chúng ta)

---

Kết luận

Qua bài này chúng ta đã nắm về Loang.

Bài sau chúng ta sẽ tìm hiểu về Tìm kiếm cây khung nhỏ nhất với thuật toán Prim.

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.