Từ 1 tới 10 trên tổng số 10 kết quả

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

  1. #1
    Ngày gia nhập
    02 2008
    Bài viết
    21

    Mặc định Xử lý Bài Toán Mê Cung trên C++?

    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.

  2. #2
    Ngày gia nhập
    12 2007
    Bài viết
    6

    Đâ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

  3. #3
    Ngày gia nhập
    11 2007
    Bài viết
    47

    Đầ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

  4. #4
    Ngày gia nhập
    12 2007
    Bài viết
    28

    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.

  5. #5
    Ngày gia nhập
    08 2008
    Nơi ở
    Liên Bang Nga
    Bài viết
    46

    . 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
    Attached Files Attached Files
    Tôi thường thích những cái gì mà tôi không bao giờ có được...

  6. #6
    Ngày gia nhập
    04 2009
    Nơi ở
    Gầm cầu
    Bài viết
    2,230

    Mặc định Xử lý Bài Toán Mê Cung trên C++?

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

  7. #7
    Ngày gia nhập
    07 2010
    Nơi ở
    chỗ kín
    Bài viết
    446

    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.

  8. #8
    Ngày gia nhập
    10 2012
    Bài viết
    2

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

  9. #9
    Ngày gia nhập
    09 2014
    Bài viết
    1

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

  10. #10
    Ngày gia nhập
    02 2013
    Nơi ở
    Ho Chi Minh City, Vietnam, Vietnam
    Bài viết
    78

    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,...

Các đề tài tương tự

  1. Chuyên cung câp váy, đầm nữ sỉ và lẻ giá tốt trên toàn quốc 2013
    Gửi bởi ngodanh trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 06-07-2013, 08:57 PM
  2. cung cấp dịch vụ thiết kế website giá rẻ trên toàn quốc
    Gửi bởi phongdv166 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 05-04-2013, 10:30 AM
  3. Cung cấp máy lọc nước nano Geyser trên toàn quốc
    Gửi bởi nguyenrong trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 16-08-2012, 02:33 PM
  4. Website cung cấp usb 3g các loại trên toàn quốc
    Gửi bởi usb3g trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 21-12-2011, 01:26 PM
  5. deploy ASP.NET cung voi SQLServer trên máy khác?
    Gửi bởi ron321 trong diễn đàn Thắc mắc lập trình ASP.NET
    Trả lời: 2
    Bài viết cuối: 02-03-2011, 02:37 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn