Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 15 kết quả

Đề tài: Đường hầm bí mật? Mê cung nhiều lối ra. Giúp mình giải thuật??

  1. #1
    Ngày gia nhập
    05 2009
    Bài viết
    3

    Wink Đường hầm bí mật? Mê cung nhiều lối ra. Giúp mình giải thuật??

    Em có 1 đề toán như sau :

    Trong các lâu đài cổ ở châu Âu người ta thường xây dựng các đường hầm bí mật để thoát hiểm trong các trường hợp khẩn cấp. Các đường hầm chỉ có thể vào từ một cửa vào duy nhất tại phòng Trung tâm và thoát ra ở rất nhiều của ra. Các cửa ra đều nằm ở rìa lâu đài, do vậy, nếu thoát ra được rìa lâu đài thì coi như đã thoát hiểm. Để nguỵ trang, người ta cho đào nhiều nhánh hầm cụt và cửa vào giả. Ngoài ra, để tăng khả năng thoát hiểm, người ta còn xây dựng các đường hầm giao nhau tại một số vị trí. Để nghiệm thu công trình, chủ lâu đài cần kiểm tra xem từ phòng trung tâm có thể thoát hiểm qua hệ thống đường hầm hay không. Hãy lập trình giúp chủ lâu đài kiểm tra hệ thống trên. Biết rằng lâu đài là một hình vuông được chia lưới ô vuông gồm n dòng, n cột. Trên hoạ đồ, ô ở dòng I cột j được ghi số 1 nếu có đường hầm, số 0 nếu không có (ô ở góc trên trái có toạ độ (0, 0)). 2 ô chỉ có thể thông nhau nếu chúng có chung cạnh.
    Dữ liệu nhập vào từ tập tin văn bản DUONGHAM.IN gồm:
    - Dòng đầu chứ 3 số nguyên dương n (n<=50), D, C (D, C là dòng và cột của phòng trung tâm).
    - N dòng tiếp theo, mỗi dòng chứa n số là các số ở các vị trí tương ứng trên hoạ đồ.
    Kết quả tìm được ghi ra tập tin văn bản DUONGHAM.OUT. Dòng đầu chứa số m là số ô phải đi qua, nếu không thoát được thì m=-1. Trong trường hợp thoát được, m dòng tiếp theo, m dòng tiếp theo: mỗi dòng chứa 2 số là số hiệu dòng cột của các ô phải đi qua theo đúng trình tự của một cách thoát hiểm.


    -- Bài toán này có giống bài toán mở rộng của tìm đường ra của mê cung tại 1 vị trí bất kỳ không ? Có thể dùng thoạt toán nào để giải quyết bài toán này ?
    -- Ai có Code bài này cho em xin để tham khảo với ...
    Đã được chỉnh sửa lần cuối bởi nguyenhaphap : 18-05-2009 lúc 12:26 AM.

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

    1 - Cậu đưa cái đề lên dòng chữ màu đỏ nhìn rất phản cảm....!
    2 - ở đây ko có code hộ đâu bạn ạ nếu muốn thì tự code, sai thì sửa? P.s: bài viết sẽ được move vào ngày mai vì &quot;phạm luật&quot;

  3. #3
    Ngày gia nhập
    05 2009
    Bài viết
    3

    sorry vì mod không thích màu đỏ. Mình không nhờ code hộ. Chỉ hỏi nếu ai có sẵn thì " có thể " gửi cho mình thôi.
    Còn câu hỏi chính là : dùng thuật toán nào để giải bài toán ? Hướng giải quyết.

  4. #4
    Ngày gia nhập
    04 2008
    Bài viết
    336

    cậu nghe tới Deep-First-Search hay A* chưa ? Cứ theo cách đó mà làm.
    code ra gió bão

  5. #5
    Ngày gia nhập
    05 2009
    Bài viết
    3

    Breadth-First-Search hay Deep-First-Search mình thấy các thuật toán mê cung thường dùng BFS. Có thể mở rộng cách tìm kiếm 1 lối ra của mê cung bằng mê cung nhiều lối ra không ?
    Để sửa lại màu khác cho dễ đọc...

  6. #6
    Ngày gia nhập
    04 2008
    Bài viết
    336

    Mặc định Đường hầm bí mật? Mê cung nhiều lối ra. Giúp mình giải thuật??

    một hay nhiều thì đó cũng chỉ là "lối ra", cứ gặp "lối ra" thì in ngược lại đường đi thôi.
    code ra gió bão

  7. #7
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Bài này dùng BFS sẽ tiện hơn rất nhiều, cài đặt đơn giản. Có thể tận dụng luôn ma trận lưu đường hầm để lưu vết. ^^

    Cheers

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

    Mình chưa hiểu rõ DFS nếu giải quyết bài toán này như sẽ như thế nào:
    - Có phải khi sử dụng DFS hoặc BFS thì sẽ phải duyệt nXn lần trong một lần lưu vết. Nếu là vậy thì bài toán có kích thước lớn 1 tý liệu có chạy được không.
    - Mình thì làm theo cách sử lý lưới. Tạo một mảng b[1,0,-1,0][0,1,0,-1] và sẽ lan từ tọa độ phòng trung tâm theo mảng b[].

  9. #9
    Ngày gia nhập
    04 2008
    Bài viết
    336

    DFS với BFS chỉ khác nhau về ý nghĩa thôi, 1 cái cứ cắm đầu mà đi, lợi về không gian, hại về thời gian. Cái kia ngược lại.

    Ngoài ra DFS cũng có thể được sử dụng trong thuật toán Sinh mê cung nữa.
    code ra gió bão

  10. #10
    Ngày gia nhập
    10 2006
    Nơi ở
    Rừng Amazon
    Bài viết
    101

    Quả là lâu lắm rồi mới thấy có người trả lời topic này, tự dưng hôm nay nhận được email mới tham gia lại.

    Để giải quyết bày toán này, không nên máy móc.

    Điều máy móc thứ 1 : Việc duyệt NxN đỉnh trong đồ thị chỉ là áp dụng với các đồ thị được lưu bởi ma trận liên kết, việc duyệt đó giúp ta tìm được các đỉnh có liên kết với 1 đỉnh có sẵn. Trong bài toán này, các đỉnh của đồ thì được liên kết với nhau theo kiểu 'mê cung', do đó không cần 1 ma trận liên kết để lưu trữ đồ thị, và rõ ràng là từ 1 đỉnh bạn dễ dàng tìm được 4 đỉnh xung quanh có liên kết với nó (cứ bỏ qua các đỉnh khác vì nó không liên kết). Do đó, bạn chỉ cần chạy với Nx4 (chứ không NxN đâu ^^). Nếu bạn cần tìm 1 cái tên trong các cách lưu trữ đồ thì để chỉ cho cái đồ thị mê cung này, thì đấy là 'lưu trữ đồ thị theo danh sách kề'.

    Điều thứ 2 : thuật toán BFS giúp ta đảm bảo được khi tìm được đường đi thì đó là đường đi ngắn nhất, trong các sách đều viết rằng : 'BFS tìm đường đi ngắn nhất giữa 2 đỉnh của đồ thị', như vậy trong trường hợp cần tìm đường đi ngắn nhất từ 1 đỉnh đến '1 tập đỉnh' của đồ thị thì ta phải làm thế nào? Chỉ là một chút sửa đổi thuật toán sẽ giải quyết được vấn đề. Cụ thể trong bài toán này, đỉnh bắt đầu là phòng trung tâm, tập đỉnh kết thúc là các đường biên bên ngoài.

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

  1. Giải thuật shaker sort. Giúp mình giải thuật với?
    Gửi bởi nguyenhai trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 29-01-2015, 10:53 PM
  2. Bài tập C Cần giải giúp 3 câu trong đề thi kĩ thuật lập trình C và Cấu trúc dữ liệu và giải thuật
    Gửi bởi nguyenthi0602 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2012, 08:42 PM
  3. Trả lời: 0
    Bài viết cuối: 16-05-2012, 02:35 PM
  4. Bài tập C++ viết hàm thực hiện thuật toán đi qua mê cung ( các bạn giúp mình)
    Gửi bởi zhuuvanz trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 05-03-2011, 04:21 AM

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