Mê cung là một đồ thị vô hướng bao gồm N
đỉnh, được mã số từ 1 đến N, với các cạnh, mỗi cạnh nối hai đỉnh nào đó với
nhau. Cho hai đỉnh S và T trong một mê cung. Hãy tìm một đường đi bao gồm các
cạnh gối đầu nhau liên tiếp bắt đầu từ đỉnh S, kết thúc tại đỉnh T sao cho
không qua đỉnh nào quá một lần.
Dữ liệu vào: Tệp văn bản tên MECUNG.INP với cấu
trúc như sau:
-
Dòng đầu tiên,
được gọi là dòng 0, chứa ba số tự nhiên N,
S và T ghi cách nhau bởi dấu
cách, trong đó N là số lượng đỉnh của
mê cung, S là đỉnh xuất phát, T là đỉnh kết thúc.
-
Dòng thứ i, i = 1..(N - 1) cho biết có hay không cạnh nối đỉnh i với đỉnh j, j = (i + 1)..N.
Thí
dụ:
|
MECUNG.INP
|
|
9 6 7
1 0 1 1 1 0 0 0
1 1 0 0 0 0 0
0 0 0 1 0 0
0 1 1 0 0
0 0 0 0
0 0 0
0 0
1
|
cho biết:
-
Dòng 0: 9 6 7 -
mê cung gồm 9 đỉnh mã số 1..9, cần tìm đường đi từ đỉnh 6 đến đỉnh 7.
-
Dòng 1: 1 0 1 1 1
0 0 0 - đỉnh 1 được nối với các đỉnh 2, 4, 5, và 6. Không có cạnh nối đỉnh 1
với các đỉnh 3, 7, 8 và 9.
-
...
-
Dòng 8: 1 – đỉnh
8 có nối với đỉnh 9.
Vì đồ thị là vô hướng nên cạnh nối đỉnh x với đỉnh y cũng chính
là cạnh nối đỉnh y với đỉnh x.
Thông tin về đỉnh N không cần
thông báo, vì với mỗi đỉnh i ta chỉ
liệt kê các đỉnh j > i tạo thành
cạnh (i, j).
Kết quả ra ghi trong tệp văn bản MECUNG.OUT:
-
Dòng đầu tiên ghi
số tự nhiên k là số đỉnh trên đường
đi từ s đến t, nếu vô nghiệm, ghi số 0.
-
Từ dòng tiếp theo
ghi lần lượt các đỉnh có trên đường đi.
Với thí dụ đã cho kết quả có thể là:
|
MECUNG.OUT
|
|
5
6
4 2 3 7
|
Từ đỉnh 6 có thể đến được đỉnh 7, qua 5 đỉnh theo đường bốn khúc:
6 ® 4 ® 2 ® 3 ® 7.
Với mê cung đã cho, nếu yêu cầu tìm đường đi từ đỉnh 6 đến đỉnh 9, tức
là với dữ liệu vào như trên thì sẽ nhận
được kết quả 0 với ý nghĩa là không có đường đi từ đỉnh 6 đến đỉnh 9, do mê
cung đã cho không liên thông, đỉnh 6 và đỉnh 9 nằm trong hai vùng liên thông
khác nhau.
Thuật toán
Xuất phát từ đỉnh v[1] = s, mỗi bước lặp i ta thực hiện các kiểm tra sau. Gọi k là số đỉnh đã đi qua và được tích luỹ
trong mảng giải trình đường đi v, cụ
thể là xuất phát từ đỉnh v[1] = s, sau một số lần duyệt ta quyết định
chọn đường đi qua các đỉnh v[1], v[2], v[3],…, v[k]. Có thể gặp các tình huống sau:
a) (Đến đích?) nếu v[k] = t tức là đã đến được đỉnh t: thông báo kết quả, dừng thuật toán,
ngược lại thực hiện b.
b) (Thất bại?) k = 0: nếu đã
quay trở lại vị trí xuất phát v[i] = s
mà từ đó không còn đường đi nào khác thì phải lùi một bước nữa, do đó k = 0. Trường hợp này chứng tỏ bài toán
vô nghiệm, tức là, do đồ thị không liên thông nên không có đường đi từ đỉnh s đến đỉnh t. Ta thông báo vô nghiệm và dừng thuật toán.
c) (Đi tiếp?) nếu từ đỉnh v[k] tìm được một cạnh chưa đi qua và dẫn
đến một đỉnh i nào đó thì tiến theo
đường đó, nếu không: thực hiện bước d.
d) (Lùi một bước) Bỏ đỉnh v[k], lùi lại đỉnh v[k-1].
Thuật toán trên có tên là sợi chỉ
Arian được phỏng theo một truyền thuyết cổ Hy Lạp sau
đây. Anh hùng Te-dây phải tìm diệt con quái vật nhân ngưu (đầu người, mình
trâu) Minotav ẩn náu trong một phòng của mê cung có nhiều ngõ ngách rắc rối đã
từng làm lạc bước nhiều dũng sĩ và những người này đều trở thành nạn nhân của
Minotav. Người yêu của chàng Te-dây là công chúa của xứ Mino đã đưa cho chàng
một cuộn chỉ và dặn chàng như sau: Chàng hãy buộc một đầu chỉ vào cửa mê cung
(phòng xuất phát s), sau đó, tại mỗi phòng trong mê cung, chàng hãy tìm xem có
Minotav ẩn trong đó không. Nếu có, chàng hãy chiến đấu dũng cảm để hạ thủ nó
rồi cuốn chỉ quay ra cửa hang, nơi em trông ngóng chàng. Nếu chưa thấy Minotav
tại phòng đó, chàng hãy kiểm tra xem chỉ có bị rối hay không. Cuộn chỉ bắt đầu rối khi nào từ phòng chàng đứng có hai sợi chỉ
đi ra hai cửa khác nhau. Nếu chỉ rối như vậy, chàng hãy cuộn chỉ để lùi lại một
phòng và nhớ đánh dấu đường đã đi để khỏi lạc bước vào đó lần thứ hai.
Nếu không gặp chỉ rối thì chàng hãy yên tâm dò tìm
một cửa chưa đi để qua phòng khác. Đi đến đâu chàng nhớ nhả chỉ theo đến đó.
Nếu không có cửa để đi tiếp hoặc từ phòng chàng đang đứng, mọi cửa ra đều đã
được chàng đi qua rồi, thì chàng hãy cuốn chỉ để lùi lại một phòng rồi tiếp tục
tìm cửa khác.
Ta xuất phát từ sơ đồ tổng quát cho lớp bài toán quay lui.
(* Pascal *)
(*----------------------------------------
MC - Tim duong trong
me cung
(Thuat toan
Arian)
s: dinh xuat phat
t: dinh ket.
------------------------------------------*)
procedure MC;
var i: byte;
begin
Doc; {doc du
lieu}
{----------------------------
khoi tao mang d,
danh dau cac
dinh da tham:
d[i] = 1: dinh
da tham
d[i] = 0: dinh
chua tham
-----------------------------}
fillchar(d,sizeof(d),0);
k := 1; {k – dem
so dinh da chon }
v[k] := s; {dinh xuat phat }
d[s] := 1; {da
tham dinh s }
repeat
if v[k] = t
then {den dich }
begin
ket(k); {ghi
ket qua: giai trinh duong di }
exit;
end;
if k < 1
then {vo nghiem }
begin
ket(0);
exit;
end;
i := Tim;
{tu dinh v[k] tim 1 dinh chua tham i
}
if i > 0
then
{neu
tim duoc, i > 0, di den dinh i }
NhaChi(i)
else CuonChi;
{neu khong tim duoc, }
{ i = 0: lui 1 buoc - bo dinh v[k] }
until false;
end;
Thủ tục Doc - đọc dữ liệu từ tệp MECUNG.INP vào mảng hai chiều a. Đây chính là ma trận kề của đồ
thị biểu diễn mê cung. Mảng a sẽ đối xứng vì mê cung là đồ thị vô hướng. Đây
cũng chính là lí do giải thích dữ liệu vào chỉ cho dưới dạng nửa trên của ma
trận kề.
(*-------------------------
Doc du lieu
------------------------*)
procedure Doc;
var i,j: byte;
begin
assign(f,fn);
reset(f);
read(f,n,s,t);
fillchar(a,sizeof(a),0);
if (n < 1)
or (n > MN) then exit;
for i := 1 to n-1 do
for j := i+1 to n do
begin
read(f,a[i,j]);
a[j,i]
:= a[i,j]; {lay doi xung }
end;
close(f);
end;
Thủ tục Xem
– hiển thị dữ liệu trên màn hình để kiểm tra việc đọc có đúng không. Với những
người mới lập trình cần luôn luôn viết thủ tục Xem. Khi nộp bài thì có thể bỏ lời gọi thủ tục này. Các
hằng kiểu string bl = #32 là mã ASCII của dấu cách, hằng nl = #13#10 là một xâu
chứa hai kí tự điều khiển có mã ASCII là xuống dòng #13, tức là ứng với phím RETURN và đưa con
trỏ màn hình về đầu dòng #10. Khi đó lệnh writeln sẽ tương
đương với lệnh write(nl).
(*------------------------
Xem du lieu
-------------------------*)
procedure xem;
var i,j: byte;
begin
write(nl,n,bl,s,bl,t,nl);
for i := 1 to
n do
begin
for j
:= 1 to n do
write(a[i,j],bl);
write(nl);
end;
end;
Thủ tục Ket(k) - ghi đường đi v[1..k] từ s đến t tìm được vào tệp output.
Ket(0): thông báo vô nghiệm.
(*------------------------------
Ghi ket qua.
k = 0: vo nghiem
k > 0: co
duong tu s den t
gom k canh
------------------------------*)
procedure
Ket(k: byte);
var i: byte;
begin
assign(g,gn); rewrite(g);
write(g,k,nl);
if k > 0
then
begin
write(g,v[1]);
for i
:= 2 to k do
write(g,bl,v[i]);
end;
close(g);
end;
Hàm Tim - từ đỉnh v[k] tìm một bước đi đến đỉnh i. Điều kiện: i phải là đỉnh chưa thăm và đương nhiên có cạnh đi từ v[k]
đến i, nghĩa là giá trị a[v[k], i]
trong ma trận kề phải là 1. Ta dùng một mảng d đánh dấu đỉnh i đã thăm chưa. d[i] = 0 – đỉnh i
chưa thăm, d[i] = 1 – đỉnh i đã thăm
và đã từng được chọn để đưa vào mảng v
là mảng giải trình đường đi. Nếu tìm kiếm thành công ta gán cho hàm Tim giá trị i,
chính là đỉnh cần đến. Ngược lại, khi việc tìm kiếm thất bại, nghĩa là không
tìm được đỉnh i để có thể đi từ đỉnh v[k]
đến đó, ta gán cho hàm Tim giá trị 0.
Ta lưu ý là mỗi đỉnh chỉ đi đến không quá một lần. Đương nhiên
khi lùi thì ta buộc phải quay lại đỉnh đã đến, do đó, chính xác hơn ta
phải gọi d[i]=1 là giá trị đánh dấu khi tiến đến đỉnh i.
(*-------------------------------------
Tu dinh v[k] tim duoc mot buoc di
den dinh i.
Dieu kien:
d[i] = 0 - dinh i chua xuat hien
trong
lich trinh v
d[i] = 1 - dinh
i da xuat hien
trong
lich trinh v.
--------------------------------------*)
function Tim:
byte;
var i: byte;
begin
Tim := 0;
for i := 1 to n do
if d[i] = 0
then {dinh i chua tham }
if a[v[k],i] =
1 {co duong tu v[k] den i }
then
begin
Tim := i;
exit;
end;
end;
Nếu tìm được đỉnh chưa thăm thoả các điều kiện nói trên ta tiến thêm
một bước theo cạnh (v[k], i).
Ta cũng đánh dấu đỉnh i là đã thăm
bằng lệnh gán d[i]: = 1. Đó là nội dung của thủ
tục NhaChi (nhả chỉ).
(*---------------------------
Di 1 buoc tu v[k]
den i
----------------------------*)
procedure
NhaChi(i: byte);
begin
inc(k);
v[k] := i; {tien them 1 buoc }
d[i] := 1; {danh
dau dinh da qua }
end;
Nếu từ đỉnh v[k] ta không tìm được
đỉnh nào để đi tiếp thì ta phải thực hiện thủ tục CuonChi (cuộn chỉ) như dưới đây. Thủ tục này chỉ đơn giản là lùi
một bước từ đỉnh Te-dây hiện đang đứng trở về đỉnh trước đó, nếu có, tức là k ³ 1, ta đánh dấu cạnh (v[k
- 1], v[k]) là đã đi hai lần. Ta nhận xét rằng, nếu không tính lần trở lại một
đỉnh khi phải lùi một bước thì mỗi đỉnh trong mê cung chỉ cần thăm tối đa là
một lần, do đó thay vì đánh dấu cạnh ([v[k - 1], v[k]) ta chỉ cần đánh dấu
đỉnh v[k] là đủ.
(*-------------------------------------
Lui 1 buoc vi tu
dinh v[k] khong
co kha nang nao dan den ket qua
-------------------------------------*)
procedure
CuonChi;
begin
dec(k);
end;
(* Pascal *)
(*------------------------------------
MECUNG.PAS Tim duong trong me cung
-------------------------------------*)
{$B-}
uses crt;
const
MN = 100; {So dinh toi da }
fn = 'MECUNG.INP'; {input file }
gn = 'MECUNG.OUT'; {output file }
nl = #13#10; {xuong dong moi }
bl = #32; {dau cach }
type
MB1 = array[0..MN] of byte;
MB2 = array[0..MN] of MB1;
var
a: MB2; {ma tran ke, doi xung }
v: MB1; {vet tim kiem }
d: MB1; {danh dau dinh da chon }
n: byte; {so dinh }
s: byte; {dinh xuat phat }
t: byte; {dinh ket thuc }
k: byte; {buoc duyet }
f,g: text; {f: input file; g: output file}
(*-----------------------
Doc du lieu
------------------------*)
procedure Doc; tự viết
(*------------------------
Xem du lieu
-------------------------*)
procedure xem; tự viết
(*---------------------------------------
Ghi ket qua.
k = 0: vo nghiem
k > 0: co
duong tu s den t gom k canh
----------------------------------------*)
procedure
Ket(k: byte); tự viết
(*--------------------------------------------
Tu dinh v[k] tim
duoc mot buoc di den dinh i.
Dieu kien:
d[i] = 0 -
dinh i chua xuat hien
trong
lich trinh v
d[i] = 1 - dinh
i da xuat hien
trong lich trinh v,
---------------------------------------------*)
function Tim:
byte; tự viết
(*---------------------------
Di 1 buoc tu v[k] den i
----------------------------*)
procedure
NhaChi(i: byte); tự viết
(*-------------------------------------
Lui 1 buoc vi
tu dinh v[k] khong co kha nang nao
dan den ket
qua
-------------------------------------*)
procedure
CuonChi; tự viết
(*-------------------------------
Tim duong trong me cung
(Thuat toan Soi chi Arian)
s: dinh xuat phat
t: dinh ket.
-------------------------------*)
procedure MC;
tự viết
BEGIN
MC; write(nl,'fini');
END.
Với thí dụ đã cho trong đề bài, bạn hãy chạy thử chương trình MECUNG.PAS với hai dữ liệu kiểm thử, một dữ liệu kiểm thử có
nghiệm và một dữ liệu kiểm thử vô nghiệm.
Chú ý
Đường đi tìm được không phải là đường ngắn nhất. Trong chương 7 ta sẽ
dùng thuật giải Dijkstra để tìm đường đi ngắn nhất.
