Tìm đường trong mê cung

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.