[Thuật toán] Loang trên ma trận

THUẬT TOÁN LOANG TRÊN MA TRẬN (DÃY 2 CHIỀU)

------Tư tưởng của thuật toán loang thật ra cũng rất đơn giản. Hãy tưởng tượng có một nàng công chúa bị bắt giam vào 1 mê cung, nàng bí quá, lôi ĐTDĐ ra fone cho hoàng tử. Hoàng tử tức tốc dẫn theo một đạo quân (giả sử rằng số quân của chàng ta là ko giới hạn). Khi đến cổng vào mê cung, chàng may mắn gặp một "bậc thánh nhân", người cho chàng biết rằng công chúa đang bị giam trong phòng [X,Y] nào đó. À, bây giờ trong đầu chàng nghĩ đến 2 hướng sau:
_ Chàng quyết định solo đi vào mê cung, dĩ nhiên trên tay cầm 1 cuộn chỉ. Khi vào cổng, chàng bắt gặp T căn phòng, chàng sẽ đi vào từng phòng một, bước vào T1, chàng lại gặp T2 cửa, ... , cứ thế đến khi ko có đường đi, chàng sẽ lần ngược theo đường chỉ, đánh dấu vào cánh cửa chàng đã đi rồi, và chọn 1 cửa khác. Với cách này, chàng sẽ tìm được phòng có công chúa, dĩ nhiên, nếu chàng ko gục ở giữa đường.
_ Tận dụng nguồn binh lực hùng hậu của mình, chàng ra hiệu lệnh "Toàn lực lục soát". Đi vào mê cung, bắt gặp T căn phòng, chàng chia đoàn binh thành T đạo, cứ thế. Dĩ nhiên, mỗi binh sĩ đều đc trang bị phương tiện liên lạc để khi tìm thấy công chúa sẽ phát hiệu lệnh "Rút lui". Vậy, với cách này ta sẽ tìm được công chúa với quãng đường đi từ cửa mê cung đến phòng giam là ngắn nhất. Nhưng, nảy sinh một bất cập là, nếu binh sĩ tìm được công chúa rồi, thì làm sao lần ra lại cửa mê cung đây??? Đương nhiên hoàng tử ko thể chấp nhận chuyện để người yêu mình chung phòng với một đám binh sĩ ~~. Chàng ra lệnh rằng, trước khi vào mỗi cửa, phải dùng kiếm vạch mũi tên xuống đất, mũi tên này sẽ hướng đến cửa các binh sĩ đã đi vào trước khi gặp căn phòng. Ví dụ khi vào cổng mê cung, 1 tốp binh sĩ đi vào cửa T1, gặp N2 cửa khác, chia binh lực ra, với mỗi cửa T2, các binh sĩ sẽ vạch mũi tên hướng về cửa T1, tức cửa đã dẫn họ tới N2 căn phòng. Nhờ đó họ sẽ lần được đường thoát khỏi mê cung.

Từ đây, ta sẽ hình thành 2 phương pháp tìm đường đi, trong bài viết này, chúng ta sẽ tìm hiểu cách thứ hai, mà theo cách gọi thông thường là LOANG: Từ một vị trí có tọa độ A(x,y) cho sẵn, bạn buộc phải tìm đến một vị trí B(x’,y’) sao cho quảng đường đi là ít nhất có thể và in ra đường đi từ A đến B đó.

------Có khá nhiều phương pháp tìm đường đi, trong đó có BFS (Breadth First Search - Tìm kiếm theo chiều rộng, còn gọi là loang), DFS (Depth First Search - Tìm kiếm theo chiều sâu). Như đã nói, chúng ta chỉ xem xét về BFS trong bài viết này. Có nhiều cách cài đặt BFS như là hàng đợi (queue) hoặc dùng 2 mảng tính qua lại lẫn nhau (mảng chứa những phòng có thể đi tiếp, và mảng chứa những phòng bắt gặp khi đi vào những phòng ở trên). Tuy nhiên các mà tôi sắp giới thiệu cho bạn đây là một cách không chính thống, phương pháp này loang theo chiều rộng và cách thức tốn khá nhiều tài nguyên. Song, với thuật toán Loang này, bạn sẽ dễ dàng làm những bài toán Loang đơn giản hay phức tạp với dữ liệu yêu cầu nhỏ. Thuật toán được trình bày ngắn gọn như sau:

------Cứ một nơi bạn đặt chân tới và thấy là nơi cho phép thì đánh dấu nơi đó với 1 số [i]k tăng dần (để xác định rằng bạn đã đi đến đó và ô đó là nơi bạn đi đến lần thứ k). Cứ tiếp tục như thế cho đến khi gặp điểm dừng thì thoát khỏi chương trình.

------Tôi xin mô tả thuật toán bằng đoạn code sau:

Code:

var  a        :  array[1..100,1..100] of byte;
          Near    :  array[1..2] of record
                                                  x,y : byte;
                                          end;
    Procedure Loang;
    Var i,j,z : byte;
    Begin
            Repeat  {Kiểm tra nếu phần tử cuối cùng a[n,m] khác 0 (gặp điểm dừng) thì sẽ kết thúc, ngược lại thì làm những công việc sau }
                  Flag := false; {Hiện tại, chưa tìm đc chỗ để loang}
                  For i := 1 to n do
                    For j := 1 to m do {Duyệt tất cả phần tử mảng}
                    Begin
                              If (a[i,j] = e) then  {Nếu phát hiện có dấu chân đc đánh dấu tại bước loang thứ e thì bắt đầu loang tiếp}
                              Begin
                                          {Tạo những phần tử xung quanh i,j. Ở đây tôi làm dưới và phải}
                                          Near[1].x := i+1;          Near[1].y := j;
                                          Near[2].x := i;            Near[2].y := j+1;
   
                                          For z := 1 to 2 do {Bắt đầu duyệt các phần tử xung quanh đó}
                                          Begin
                                                  If (a[Near[z].x,Near[z].y] = 0) then {Nếu kô gặp chướng ngại vật}  (Near là mảng hằng giống như trong bài toán mã đi tuần}
                                                  Begin
                                                          Flag := true; {Đã tìm được chỗ loang}
                                                          a[Near[z].x,Near[z].y] := e+1; {Đánh dấu chân đã loang tới đếm được ở bước thứ e + 1}
                                                  End;       
                                          End;
                              End;
                    End;
                  If  Flag then e := e+1;
            Until a[n,m] <> 0;
    End;
   
    BEGIN
            ReadInput;
            e := 1;
            Loang;
            Print;
            Readln;
    END.


Thực tế cho thấy, kết quả của bài toán sẽ in ra 1 ma trận đã được loang "tá lả". Bởi vì bạn không kiểm soát và cho biết một đường loang nhất định, do đó từ 1 bước sẽ có nhiều hướng đi.

Okay, để giải quyết vấn đề này, công việc chỉ còn là ở bạn. Tôi đã cung cấp cho bạn cách Loang ra toàn ma trận, nhiệm vụ của bạn bây giờ là hãy dùng cách tương tự để viết một thủ tục xóa những Loang dư thừa, không cần thiết.
Vd:

Ma trận gốc:
0 0 1 0 1
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0

Ma trận Loang:
1 2 1 0 1
2 3 4 1 1
3 4 5 6 1
4 5 6 7 8

Ma trận đã xóa Loang dư:
1 0 1 0 1
2 0 0 1 1
3 0 0 0 1
4 5 6 7 8

Xong. Thuật toán cài đặt khá đơn giản và chạy khá hiệu quả, tuy nhiên thời gian khá chậm do độ phức tạp tương O(k*n^2). Bạn có thể thêm một chút cải tiến để cải thiện tốc độ. Hy vọng bài viết bổ ích đối với bạn ;)

Nguồn:NguyenVanTo.net
Re-up by: Admin

Hay