Xử lý Bài Toán Mê Cung trên C++?

[bills_khoa]

Giả sử có một mê cung. Ta có thể đi vào từ một cổng S nào đó cho trước và sẽ đi ra ở một cổng F nào đó cho trước. Hãy viết chương trình tìm đường đi từ S đến F.

[rannek]

Đây là 1 bài có vẻ rất thú vị.Nhưng mình vẫn ko hiểu rõ đề lăm.Bạn có thể cho biết input là gì và output là gì sau đó cho 1 ví dụ được ko

[metal_shield]

Đầu vào có thể là 1 ma trận số với 1 số quy ước:

0 là vùng có thể đi được
1 là vùng ko thể đi qua
2 là cổng vào
3 là cổng ra

[blackpawn]

Mình có ý này:
Khi bắt đầu vào mê cung, ta đặt tay lên bức tường bên phải, rồi cứ từ đó đi lần theo bức tường bên phải, thì đến một lúc nào đó sẽ ra khỏi mê cung( nếu như mê cung đó có đường ra)
// tất nhiên không đảm bảo đó là con đường ngắn nhất

Lý do: khi đi như vậy thì ta không thể đi qua một nơi 2 lần.

[lienthang]

. Các bạn thân mến!
. Về bài toán mê cung này có rất nhiều các dạng biến thể khác nhau. Có một dạng tạo, và một dạng lập. Dạng tạo, là yêu cầu nhập vào kích thước một mê cung mxn, cho một điểm đầu (x_first,y_first) và một điểm cuối(x_last,y_last), yêu cầu chúng ta phải tạo ra một mê cung, với một độ phức tạp nào đó, nhưng ít nhất là tồn tại một lối đi từ (x_first,y_first) đến (x_last,y_last). Dạng lập của nó, là cho trước dữ liệu về một mê cung. Yêu cầu ta viết chương trình, dò xem trong lớp dữ liệu đã cho có tồn tại một lối đi nào từ điểm (x_input,y_input) đến điểm (x_output,y_output) hay không.
. Nói một cách khách quan, dạng tạo và dạng lập có độ phức tạp như nhau. Tuy nhiên, trên nền tảng ý tưởng đó, còn có nhiều biến thể khác của bài toán mê cung, do sự sáng tạo ngày càng cao của người lập trình. Mình cũng đã có dịp viết một ít về bài này, tuy còn sơ sài, song cũng muốn chia sẻ cùng các bạn, mong các bạn cho ý kiến
1. Chương trình này có nội dung như sau:
-Trong file inp.txt chứa thông tin về một mê cung
+Dòng thứ nhất ghi kích thước của mê cung mxn
+m dòng và n cột tiếp theo ghi thông tin về mê cung, tại điểm tọa độ (x,y) nếu giá trị là 0 thì có thể đi được tới đó, ngược lại nếu là 1 thì bị cấm
Yêu cầu:
-Trong file out.txt ghi nội dung thông tin quá trình tìm kiếm một đường đi từ điểm (1,1) đến điểm (m,n) trong mê cung.
+Nếu không tồn tại lối đi, thì báo là Noresult, nếu có lối đi, thì dòng đầu ghi rõ độ dài đường đi, các dòng tiếp theo ghi rõ lộ trình
-file Graph.txt là code mô tả đồ họa của quá trình đi từ (1,1) đến (mxn) của một con chuột khi nó bị lạc vào mê cung trên
-file MAZE.cpp là code của chương trình chính tìm đường đi, đọc và ghi dữ liệu

2. Bài này có nội dung tương tự bài 1, song tôi có mở rộng lên một chút nho nhỏ.
-file debai.txt ghi nội dung đề bài
-file inp.txt ghi nội dung kích thước mê cung mxn
điểm vào có tọa độ (x_intp,y_intp) và điểm ra có tọa độ (x_outp,y_outp)
sau đó là phần trường ma trận, 0-được đi qua, 1-bị cấm
-file out.txt ghi nội dung kết quả tìm kiếm
-file code.cpp là mã chương trình
-file graphics.txt là mã chương trình đồ họa mô phỏng

[zstar]

bài toán này dùng thuật toán Astar là hiệu quả nhất

[pkthanh92]

dùng A* như zstar nói là chuẩn đó,
cũng có thể dùng thuật toán backstracing cho đơn giản.
cái này thì nên tìm trên google mà tự ngâm cứu, nhờ người khác giải hộ thì thà không làm còn hơn.

[hoang_dn75]

sao chạy cái graphics.txt bị lỗi huhu ai giúp mình vs!!!

[zjtzjt]

ai giúp mình cái thuật toán tạo mê cung với

[luanft]

Thuật toán tạo mê cung có thuật toán PRIM. Còn tìm đường đi có nhiều cách
Tệ nhất Quay lui(thử sai)
Vừa vừa Dijkstra(vét cạn)
Tốt nhưng còn hên xui A*(sử dụng heuristic)

Ngoài ra còn nhiều phương pháp khác: Tìm đường đi bằng cách men tường,...