Đồ thị cơ bản

[quangtq]

Đọc phần này đau đầu quá. Có chỗ này mắc hỏi mọi người:
Mê cung m * n gồm các ô vuông đơn vị. Trên đó ghi kí tự:
O: Ô an toàn
X: Ô nguy hiểm
E: Ô nhà thám hiểm đứng.
Trong mê cung có đúng 1 ô E.
Tìm đường để nhà thám hiểm thoát khỏi mê cung. Để thoát khỏi thì chỉ cần đi đến 1 ô biên ((chỉ số hàng là 1 hoặc m) or (cột là 1 hoặc n)).
Nhà thám hiểm chỉ đi được đến các ô chung cạnh với ô đang đứng và ô đó an toàn. Vd ô i,j thì chỉ có thể đến các ô : (i-1,j),(i,j-1),(i,j+1),(i+1,j) nếu các ô đó là O.
Cái mắc là em không biết tổ chức dữ liệu thế nào. Thuộc vào phần đồ thị mà.
Mọi người gợi ý xây dựng cái đồ thị hộ em.
Còn việc tìm kiếm đường ra biên không khó.

[elnino_020993]

theo anh í, mấy cái bài dạng mà đi được mấy ô xung quanh, em nên xây dựng mảng hằng, cho thuận tiện. Anh vd nhe:
đi được 4 hướng như em nói, ta tạo 2 mảng

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

4 hướng này theo thứ tự em đã liệt kê ở trên, khi gọi thủ tục loang, sự chênh lệch tọa độ sẽ được xử lý rất gọn gàng nhờ 2 mảng hằng này

tạm đến đây đã

[ngtrhieu0011]

tại sao mấy bài loang BFS cơ bản lại mún giải đồ thị chi nhỉ?
này chú có biết đồ thị là gì không?

[bld]

loang , BFS là đồ thị chứ gì nữa ^^! chỉ có điều mấy bài đồ thị ở dạng đặc biệt như những bài tìm đường di chuyển trên một bảng thì loang là tốt nhất , xử lý việc chuyển hướng dùng mảng hằng..

[elnino_020993]

hix, trong cái bài này ko dùng BFS thì cùng cái gì giờ
trong mảng 2 chiều, việc đi lại tính theo số bước đi => ko phải là đồ thị có trọng số, dùng loang là thích hợp nhứt rồi còn gì nữa

[quangtq]

Thế hóa ra ko xây dựng được cái đồ thị nào à? Nếu vậy thì em đã loang từ hôm qua rồi.
Làm rồi. Còn đoạn xử lý nếu không tìm thấy đường thì thôi, phần đấy không khó.
Em tưởng xây dựng đồ thị liên kết giữa các ô trong bảng chứ.
Mọi người thử nhận xét.

Uses Crt;
Const
    Dx : array***91;1..4***93; of Integer = (-1,0,0,1);
    Dy : array***91;1..4***93; of Integer = (0,-1,1,0);
    Max = 50;
Type
    O = Record
        Row, Col : Integer;
    End;

Var
    Matrix:Array***91;1..Max,1..Max***93; of Char;
    Queue:Array***91;1..Max***93; of O;
    Trace:Array***91;1..Max,1..Max***93; of O;
    m,n,First,Last:Integer;
    xp:O;

Procedure Enter;
Var i,j:Integer;
    F:Text;
Begin
    Assign(F,'mecung.inp'); Reset(F);
    Readln(F,m,n);
    For i:=1 to m do
        Begin
            For j:=1 to n do
                Begin
                    Read(F,Matrix***91;i,j***93;);
                    If Matrix***91;i,j***93;='e' then
                        Begin
                            Xp.Row:=i;
                            Xp.Col:=j;
                        End;
                End;
            Readln(F);
        End;
    Close(F);
End;

Function Done(i,j:Integer):Boolean;
Begin
    If ((i=1) or (i=m) or (j=1) or (j=n))
        And (Matrix***91;i,j***93;='o') then Done:=True
    Else Done:=False;
End;

Function InTable(i,j:Integer):Boolean;
Begin
    If (1<=i) and (i<=m) and (1<=j) and (j<=n) then
        InTable:=True
    Else InTable:=False;
End;

Procedure Push(v:O);
Begin
    Inc(Last); Queue***91;Last***93;:=v;
End;

Function Pop:O;
Begin
    Pop:=Queue***91;First***93;; Inc(First);
End;

Procedure BFS;
Var
    i,j,k:Integer;
    u,v:O;
Begin
    Queue***91;1***93;:=xp;
    First:=1; Last:=1;
    Repeat
        u:=Pop;
        For i:=1 to 4 do
            Begin
                v.Row:=u.Row+Dx***91;i***93;;
                v.Col:=u.Col+Dy***91;i***93;;
                If (InTable(v.Row,v.Col)) and (Matrix***91;v.Row,v.Col***93;='o') then
                    Begin
                        Push(v);
                        Trace***91;u.Row,u.Col***93;:=v;
                    End;
            End;
    Until Done(v.Row,v.Col);
End;

Procedure PrintResult;
Var v:O;
Begin
    v:=xp;
    Repeat
        Begin
            Write('(',v.Row,',',v.Col,')->');
            v:=Trace***91;v.Row,v.Col***93;;
        End;
    Until Done(v.Row,v.Col);
    If Done(v.Row,v.Col) then
        Begin
            Write('(',v.Row,',',v.Col,')');
        End;
End;

BEGIN
    ClrScr;
    Enter;
    BFS;
    PrintResult;
    Readln;
END. 

Khác với mấy bài cơ bản là trace ngược thì bài này trace xuôi.
P/S: Nhân tiện, giải thích hộ em cái Tarjan, làm được nhưng ko hiểu rõ.

[ngtrhieu0011]

chán thật, BFS đâu phải là đồ thị =))
BFS, DFS là 2 cách "duyệt", dùng để duyệt mảng và đồ thị, chớ nhầm BFS là đồ thị.

Đồ thị là 1 tập hợp gồm U đỉnh và V cạnh, mỗi cạnh nỗi 2 đỉnh.

[quangtq]

1. Ai chả biết cái anh nói.
2. Bài này nằm trong phần Đồ thị nên em hỏi thế.
Hỏi phải biết mình hỏi cái gì chứ. Học Đồ thị mà ko biết nó là cái gì à.
Em không giỏi nhưng cũng ko quá ngu đâu.
x-(

[ngtrhieu0011]

em đọc bài này trong cuốn nào thế ???

[quangtq]

Cuốn của LMH
==============================