DANH SÁCH BÀI VIẾT Tìm hiểu thuật toán Quy hoạch động Tìm hiểu về Hàm đệ quy Thuật toán tìm kiếm nhị Tìm hiểu về Thuật toán quay lui (Backtracking) Tìm hiểu thuật toán Loang Tìm hiểu thuật toán chia để trị Tìm hiểu thuật toán tham lam trong lập trình Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search) Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search) Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)
Thuật toán Loang là một thuật toán rất hay và được ứng dụng nhiều trong các bài toán thực thực tế như, tìm đường đi, dò mìn, tô màu….Vậy trong bài viết này cùng blog tuicocach.com tìm hiểu thuật toán này nhé.
Thuật toán Loang trong lập trình
Thuật toán Loang hay chúng ta còn gọi với cái tên là thuật toán vết loang dầu. Gọi là thuật toán loang vì nguyên lí của thuật toán này rất giống với hiện tượng loang sảy ra của chất lỏng. Khi ta đổ dầu xuống một mặt phẳng khô, dầu sẽ có hiện tượng loang dần ra những khu vực xung quanh.
Tương tự, thuật toán loang cũng áp dụng nguyên lý đó, từ 1 điểm ban đầu ta loang dần thuật toán ra các hướng khu vực xung quanh.
Trước khi tìm hiểu thuật toán loang thì bạn nên phải biết trước Hàm đệ quy đã, đệ quy thì nó cũng chỉ đơn giản là một hàm mà bên trong nó gọi lại chính hàm đó để thực hiện lại một khối lệnh y xì đúc.
Mình đã có một bài viết riêng về hàm đệ quy rồi, đọc tại đây nhé: Tìm hiểu về Hàm đệ quy trong lập trình
Mô hình thuật toán
Mã giả cho thuật toán Loang.
void Loang(chiều chieu1, chiều chieu2, chiều chieu3......)
{
if(Điều kiện tiếp tục thực hiện loang){
[Đánh dấu điểm đã được loang];
//Loang ra các hướng xung quanh
Loang(chieu1--, chieu2, chieu3);
Loang(chieu1++, chieu2, chieu3);
Loang(chieu1, chieu2--, chieu3);
Loang(chieu1, chieu2++, chieu3--);
Loang(chieu1, chieu2--, chieu3++);
Loang(chieu1, chieu2, chieu3--);
}
}
Chiều ở trên có nghĩa là chiều ngang, chiều dọc, chiều cao….hoặc bất kì 1 chiều nào khác mà có thể sảy ra. Trong mảng hay trong hệ trục tọa độ OXY ta gọi là chiều x, y. Mỗi một chiều thì sẽ có 2 hướng ngược nhau, ví dụ chiều dọc có hướng đi lên hoặc hướng đi xuống.
Như vậy từ một điểm ban đầu, ta sẽ loang điểm này ra các hướng xung quanh bằng cách cộng hoặc trừ 1 đơn vị. Sau khi đã loang ra các hướng xung quanh, ta lại thực hiện lặp loang từ các điểm xung quanh đó tiếp tục ra các điểm xung quanh của chúng cho đến khi tất cả các điểm đều được đi qua.
Thuật toán loang trong mảng 2 chiều
Đã là mảng 2 chiều thì tất nhiên là sẽ có 2 chiều rồi, và 2 chiều thì sẽ 4 hướng là hướng đi lên (y–), hướng đi xuống (y++), sang trái (x–), sang phải(x++).
Mình sẽ có một chương trình mô phỏng như sau, ban đầu có một mảng 2 chiều gồm 20×20 phần tử (ô vuông 400) tất cả đều là con số 0, mình sẽ lấy 1 điểm vị trí bắt đầu loang là vị trí (10,10), từ điểm này mình sẽ loang ra toàn bộ mảng và biến đổi tất cả phần tử mảng thành 1.
#include <bits/stdc++.h>
#include <windows.h>
#define MAX 20 //định nghĩa MAX là 20
using namespace std;
int a[MAX][MAX] = {0}; //Khai báo mảng A goomg MAX * MAX phần tử
//Hàm này chỉ để hiển thị mảng ra màn hình
void output(){
for(int i = 0; i < MAX; i++){
for(int j = 0; j < MAX; j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
//Hàm này chỉ với mục đích tạo độ trễ cho chương trình để bạn dễ dàng theo dõi bảng Loang
void delay(int ms){
for(int i = 0;i< 123000*ms;i++);
}
//Hàm loàng, tập chung chú ý ở hàm này thôi
int Loang(int x, int y)
{
//Điều kiện để tiếp tục Loang là vị trí đó phải chưa bị đánh dấu(ở bài này tức là điểm đó vẫn giá trị 0)
//Và điểm đó phải nằm bên trong khu vực ô vuông 20*20, tứccả x, y > 0 và phải < 20
if(a[x][y] == 0 && x >= 0 && y >=0 && x < MAX && y < MAX){
a[x][y] = 1; //Gán điểm đó giá trị bằng 1
system("cls"); //Lệnh này là lênh xóa màn hình
output(); //Hiển thị lại mảng sau khi đã gắn lại phần tử đó bằng 1
delay(1000); //Tạm dừng 1 khoảng thời gian ngắn để dễ dàng theo dõi vết loang ra sao
Loang(x--, y); //Thực hiện loang qua hướng trái
Loang(x++, y); //Thực hiện loang qua hướng phải
Loang(x, y--); //Loang lên hướng trên
Loang(x, y++); //Loang xuống hướng dưới
}
}
int main()
{
Loang(10,10); //Gọi Loang bắt đầu tại vị trí (10,10)
}
Hình ảnh chụp quá trình chạy chương trình.
Bạn coppy đoạn code trên về chạy thử nhé, chương trình đã mô phỏng rất rõ rằng thuật toán. Bạn chạy và xem các bước thực hiện của nó sẽ hiểu được thuật toán ngay thôi, thuật toán này dễ mà.
Xem tất cả bài viết về chủ đề C/C++ tại đây nhé.
