Thuật toán loang

Đây cũng là một trong những thuật toán cơ bản mà bất kì ai khi học lập trình đều nên và cần biết.
Tư tưởng:
Tư tưởng của thuật toán dựa trên một hình ảnh rất thực tế là khi ta ném một hòn đá xuống nước, nó sẽ tạo ra sóng nước và lan đều ra các hướng.
VD:
Cho một mảng 2 chiều gồm n*m phần tử 0 hoặc 1. Hãy đếm số vùng liên thông mà chỉ gồm toàn số 1 (ở đây xét trường hợp liên thông 4 láng giềng), cho biết diện tích của vùng lớn nhất.
Input1
4 5
1 0 1 1 1
0 1 1 0 1
1 0 1 0 0
1 1 1 0 1
output1
3 (có 3 vùng)
11 (diện tích của vùng lớn nhất)
input2
3 4
0 0 1 1
0 1 1 0
1 1 1 1
output2
1 (có 1 vùng)
8 (diện tích của vùng lớn nhất)
Giải:
Ta duyệt lần lượt các phần tử từ đầu đến cuối của mảng 2 chiều. Với mỗi phần tử ở vị trí (i,j) có giá trị là 1 ta thực hiện như sau:

Code:


...
s=0;// s là diện tích của vùng đó, lúc đầu gán bằng 0
sovung=sovung+1 // đếm số vùng liên thông, khởi tạo sovung=0
Try(i,j);
...


Với thủ tục đệ quy Try(i,j):

Code:


void Try(int i, int j)
{    s=s+1;  // Tăng diện tích vùng đó lên 1 đơn vị
      if (smax<s)
          smax=s; // smax là diện tích của vùng liên thông lớn nhất cần tìm
      if(A[i+1][j]=1 && i<n)
          Try(i+1,j);
      if(A[i-1][j]=1 && i>1)
          Try(i-1,j);
      if(A[i][j+1]=1 && j<m)
          Try(i,j+1);
      if(A[i][j-1]=1 && j>1)
          Try(i,j-1);     
}


Như vậy sau khi duyệt hết mảng 2 chiều ta đã tìm được số vùng liên thông 1 là: sovung; diện tích của vùng lớn nhất là: smax