# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  Bài tập tìm đường đi ngắn nhất trong mảng 2 chiều ?

## phanloi711

Mê cung HCN kích thước m x gồm các ô vuông đơn vi (m,n<=1000).Trên mỗi ô vuông ghi 1 trong 3 kí tự: 
_ O: Nếu ô dó an toàn 
_ X: Nếu ô đó có cạm bẫy 
_ E: Nếu là ô có 1 nhà thám hiểm đang đứng 
Duy nhất chỉ có 1 ô ghi chữ E. Nhà thám hiểm có thể từ 1 ô đi sang một trong số các ô chung cạnh với ô đang đứng ( tức là có 4 ô có thể đi đến theo hàng ngang và dọc). Môt cách đi thoát khỏi mê cung là 1 hành trình đi qua các ô an toàn ra 1 ô BIÊN. Hãy chỉ cho nhà thám hiểm thoát ra khỏi mê cung đi qua ít ô nhất 
*File vào: 
*dòng đâu ghi n,m 
n dòng tiếp theo, ghi m kí tự là trạng thái của các ô trong mê cung 
*File ra:* 
Ghi hành trình, ví dụ : (i,j)->(q,w)->....

----------


## longnt

Kích thước lớn vậy thì mình nghĩ chỉ có loang :-?

----------


## quoctiepkt

Đúng loag đó bạn, nhưng mà cái cách tổ chức dữ liệu và cách truy vết thực sự rất khó, bạn có code không cho mình xin vs

----------


## chuvanduyhn91

Mình ko có code. Nhưng bạn thấy tổ chức dữ liệu, truy vết khó ở điểm nào?

----------


## vanphongquanphunhuan

> Mình ko có code. Nhưng bạn thấy tổ chức dữ liệu, truy vết khó ở điểm nào?


 Cảm ơn bạn đã quan tâm. Chẳng hạn bên BFS thông thường ta chỉ làm việc với một đỉnh của đồ thị, bây giờ ta phải làm việc với 1 ô của ma trận có hoành độ và tung độ, vậy cách loang nó trong BFS là như thế nào. 
Ta phải thành lập mảng truy vết như thế nào để sau khi loang hết ma trận, ta có thể truy vết 1 cách dễ dàng. 
Mong bạn chỉ dẫn tận tình, đây là bài căn bản cuối cùng mình học trong phần đồ thị để chuyển sang phần khác rồi ^^

----------


## dongoclinh

Mỗi bước đi thêm 1 ô ở trái, phải, trên, dưới thì bạn dùng 1 mảng hằng từ 1->4 để điều khiển việc đi này. Trong quá trình loang bạn đã sử dụng 1 hàng đợi rồi. Đến khi truy vết thì cứ lấy từ hàng đợi ấy ra thôi ^^

----------


## lamgiaseo

Bạn có thể viết cho mình code giải quyết bài này được không ? Loang này quả thật rất khó với mình ^^

----------


## hautran200594

Loang trên đồ thị và mảng 2 chiều thực chất giống nhau về nguyên lí: sử dụng queue để lưu những trạng thái tiếp theo để buớc sau xử lí. Nếu trong đồ thị lưu lại những đỉnh loang tiếp theo thì trong mảng 2 chiều bạn lưu lại tọa độ ô có thể tới được tiếp theo. Mình nghĩ code bạn có thể tự viết nếu đã thực sự hiểu về loang.

----------

