Đồ 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

:D 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[1..4] of Integer = (-1,0,0,1);
Dy : array[1..4] of Integer = (0,-1,1,0);
Max = 50;
Type
O = Record
Row, Col : Integer;
End;

Var
Matrix:Array[1..Max,1..Max] of Char;
Queue:Array[1..Max] of O;
Trace:Array[1..Max,1..Max] 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[i,j]);
If Matrix[i,j]='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[i,j]='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[Last]:=v;
End;

Function Pop:O;
Begin
Pop:=Queue[First]; Inc(First);
End;

Procedure BFS;
Var
i,j,k:Integer;
u,v:O;
Begin
Queue[1]:=xp;
First:=1; Last:=1;
Repeat
u:=Pop;
For i:=1 to 4 do
Begin
v.Row:=u.Row+Dx[i];
v.Col:=u.Col+Dy[i];
If (InTable(v.Row,v.Col)) and (Matrix[v.Row,v.Col]='o') then
Begin
Push(v);
Trace[u.Row,u.Col]:=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[v.Row,v.Col];
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. :D
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
==============================

[ngtrhieu0011]

cuốn nào của LMH, LMH có nhìu cuốn lắm ?

[bld]

cuốn DSAP textbook , e nghĩ là vậy , cuốn này của thầy LMH là số 1 ( ebook)

[ngtrhieu0011]

vậy là mình gà rồi :-? :((

[quangtq]

cuốn DSAP textbook , e nghĩ là vậy , cuốn này của thầy LMH là số 1 ( ebook)
Chuẩn!!
Ông anh đừng suy nghĩ tiêu cực thế nữa.