Bài 6: Thuật toán loang trên ma trận

Bài viết này là phần 6 trong 6 bài của Series Lý thuyết đồ thị căn bản

Thuật toán loang (Thuật toán vết dầu loang) là một trong những thuật toán được dùng khá nhiều trong tin học, điển hình là thuật toán loang trên ma trận này được ứng dụng để đếm số thành phần liên thông trên ma trận. Nó trong các trò chơi nổi tiếng như line 98, trò chơi dò mìn trên windows, tìm đường đi ngắn nhất trên ma trận…

1. Giới thiệu thuật toán vết dầu loang

Thuật toán loang có tên gọi như vậy vì nguyên lý hoạt động của nó giống vết dầu loang. Từ một vết dầu nhỏ sẽ được loang ra xung quanh. Thuật toán loang trên ma trận cũng vậy, bạn sẽ duyệt một ô trên ma trận và sau đó duyệt các điểm xung quanh nó và dần loang ra để giải quyết 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 đó để có thể dò được các bãi mìn xung quanh, và bạn sẽ làm như vậy đến khi không còn loang được nữa.

Tư tưởng của thuật toán loang chỉ có vậy, trong bài viết này mình sẽ cố gắng giới thiệu bạn rõ hơn về việc ứng dụng nó qua một vài ví dụ.

VBGRASS spoj – Bãi cỏ ngon nhất

Bài trên bạn có thể dùng thuật toán BFS hoặc DFS để loang ra từng vùng có các kí tự giống nhau. cách tổ chức code khi loang ra bạn có thể tham khảo như bài này https://kienthuc24h.com/co-ban-ung-dung-bfs-de-giai-quyet-bai-tap-duong-di-cua-quan-ma-trong-thi/ bạn sẽ khai báo như sau

Và tiến hành loang và đếm thành phần liên thông theo hướng làm như sau:

2. Code loang đếm thành phần liên thông c++

3. Bài tập minh họa

a. Đề bài toán thứ 2

Link đề bài http://www.spoj.com/THPTCBT/problems/MTKPMANG/

Khôi phục mảng

Chúng ta sẽ có một ma trận gồm các số 0,1. Và từ ma trận A chúng ta sẽ tạo được ma trận B với B[i,j] là số lượng ô có giá trị bằng 1 kề cạnh với A[i,j]

Cho trước mảng B, hãy  khôi phục mảng A.

Nếu không thể khôi phục thì ghi ra dòng chữ “KHONG THE”

b. Example

Input:
4 4
1 2 1 1
2 2 3 1
3 2 2 2
0 3 1 1

Output:
1 0 0 1
1 1 0 1
0 1 1 0
1 0 1 0

Bài toán trên cũng là tư tưởng loang nhưng lúc này chúng ta không tiếp cận chúng từ 1 vị trí, mà dựa vào các đặc điểm tối thiểu của nó để kết luận kết quả bài toán.

Ví dụ trong bài toán trên, bạn có thể đi lên từ các trường hợp, số 0 ở các góc, khi đó bạn điền được 2 số 1, số 3 ở cạnh, trường hợp số 0 điền được 4 số 1,…. ý tưởng tổng quát là vậy.

c. Code lời giải

 

d. Một số bài tập khác liên quan

bài giải MTNTRAI spoj THPTCBT – 21697. Nông Trại

BCLKCOUN spoj PTIT – Đếm số ao

BCISLAND PTIT spoj – Nước biển

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *