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.