Thuật toán Loang

Cấu trúc dữ liệu và giải thuật

0.0 (0 đánh giá)
Tạo bởi Katsu Cập nhật lần cuối 18:11 07-07-2022 2.305 lượt xem 0 bình luận
Tác giả/Dịch giả: huulam3011 K9
Học nhanh

Danh sách bài học

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ề:

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 n \times 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.

Input:

  • Dòng 1: 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})
  • Dòng 2_{\dots}n+1: 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

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.

Thuật toán Loang


Ý 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 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ạ độ (x, y), ta thấy 4 ô vuông xung quanh nó sẽ có toạ độ như sau:

Thuật toán Loang

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, y) để 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 ô (x, y) là toạ độ ô (x, y) 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}dy[]={1, -1, 0, 0} thể hiện cho các giá trị được cộng thêm vào toạ độ (x, y) để đượ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 (x, y) có thuộc hình đang xét không đó là 1\leq x\leq n && 1\leq y\leq m.


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à O(n \times m).


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ê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.

Nội dung bài viết

Tác giả/Dịch giả

Mình là Nguyễn Hữu Lâm, một người có niềm đam mê rất lớn đối với lập trình. Hiện tại, mình đang là sinh viên Khoa học máy tính của Đại học Bách Khoa Hà Nội. Mong muốn của mình là có thể chia sẻ những kiến thức mà bản thân có cho mọi người, học hỏi, kết bạn với tất cả những người có cùng đam mê với mình.


K9

Nhà sáng lập Howkteam.com, KQuiz.vn & tác giả các khóa học C#, Auto, Unity3D, Python....

Với mong muốn mang đến kiến thức chất lượng, miễn phí cho mọi người, với tâm huyết phá bỏ rào cản kiến thức từ việc giáo dục thu phí. Tôi đã cùng đội ngũ Kteam đã lập nên trang website này để thế giới phẳng hơn.
Hãy cùng chúng tôi lan tỏa kiến thức đến cộng đồng! 

Khóa học

Cấu trúc dữ liệu và giải thuật

Bạn đã từng đau đầu với các cấu trúc stack, queue,.. hoặc cảm thấy cực kỳ khó khăn với các thuật toán sắp xếp, tìm kiếm được sử dụng trong lập trình. Đừng lo lắng! Trong khoá học này, chúng ta sẽ cùng nhau tìm hiểu một cách đơn giản nhất về cấu trúc dữ liệu và giải thuật, cũng như giúp bạn nắm rõ hơn về các kiến thức này.

Hãy cùng xem cấu trúc dữ liệu và giải thuật có gì đáng sợ không nhé!

Đánh giá

Bình luận

Để bình luận, bạn cần đăng nhập bằng tài khoản Howkteam.

Đăng nhập
Không có video.