vi du thuat toan loang

  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.

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

Sau đây mình sẽ giới thiệu một cách cài đặt khác, sử dụng hàng đợi (queue) như sau:

Const

Hx:array[1..4] of shortint=(0,1,-1,0);

Hy:array[1..4] of shortint=(1,0,0,-1);

Front:=0;  Rear:=1;     {đánh dấu trong hàng đợi những phần tử cần quan tâm}

Repeat

    Inc(front);

    X:=queue[front].x;  Y:=queue[front].y;

    For  i:=1 to 4 do   {Xét các ô kề}

        If A[X+hx[i],Y+hy[i]]={đi được} then 

        Begin

            Inc(rear);   queue[rear].x:=X+hx[i];  queue[rear].y:=Y+hx[i];

            Pre[rear].x:=X;   Pre[rear].y:=Y;  {lưu đường đi}

        End;

Until Front>Rear;   {hết hàng đợi}

Bạn đang đọc truyện trên: AzTruyen.Top

Tags: