tailieunhanh - Thuật toán xây dựng mê cung

Tài liệu tham khảo về toán, cho các bạn đam mê, đào sâu hơn về kiến thức toán | VIETBOOK Thuật toán xây dựng mê cung Trong thần thoại Hi Lạp có con quỷ Minôto rất hung dữ ở trong một hang sâu. Đuờng đi vào hang là một mê cung ai có can đảm vào diệt quỷ thì cũng không dễ gì lần đuợc vào hang quỷ mà còn có thể bị lạc không tìm đuợc lối ra. Ng-ời anh hùng Têzê đã liều mình vào hang quỷ. Để giúp anh nàng Arian đã đua cho Têzê một cuộn chỉ và nàng cầm đầu mối. Khi vào mê lộ thì Têzê kéo dần cuộn chỉ đến lúc quay về thì chỉ cần cuốn chỉ lại để lần theo đó mà ra khỏi mê cung. Chuyện thần thoại thì là nhu vậy còn mê cung thì đã hấp dẫn nhiều nhà kiến trúc hoạ sĩ thi sĩ trong hàng chục thế kỉ qua. Các nhà toán học cũng chú ý đến mê cung vì nó mang nhiều ý nghĩa sâu sắc liên quan đến nhiều ngành của toán học hiện đại. Ngay trong cuộc sống thuờng ngày chúng ta cũng thuờng gặp mê cung trong các bài toán đố vui Tìm đuờng trong mê cung . Trong bài báo này tôi xin giới thiệu với các bạn một thuật toán xây dựng mê cung kích thuớc tuỳ ý. Ta xem tất cả các đuờng đi trong mê cung là một tập hợp các ô đuợc nối với nhau. Ban đầu tất cả các ô đều không đuợc nối và xung quanh tất cả các ô đều có tuờng. Lấy một bức tuờng bất kì và kiểm tra xem ô ở bên kia bức tuờng có đuợc nối bằng một đuờng đi nào đó hay không. Nếu đúng nhu vậy thử một bức tuờng khác. Nếu không thì phá bức tuờng và kết hợp hai tập hợp đuờng đi với nhau. Hình Một mê cung kích thuớc 20x20. Ta dùng một mảng hai chiều để luu lại mê cung xây dựng đuợc. Mỗi thành phần của mảng chứa giá trị 1 2 hoặc bằng 1 or 2 trong đó 1 biểu thị là ô có tuờng dọc còn 2 biểu thị ô có tuờng ngang. Ta sử dụng hai cấu trúc sau để thể hiện tập hợp đuờng đi và tập hợp tuờng. PMazeCell AMazeCell MazeCell record Trỏ tới đầu danh sách tất cả các ô có thể tới đuợc từ ô này. Dễ dàng nhận biết để có thể so sánh mset PMazeCell Trỏ tới ô tiếp theo của tập hợp các ô nối với nhau này next PMazeCell end PMazeWall AMazeWall MazeWall record Có tuờng hay không tuờng ngang hay dọc wall byte Toạ độ của bức tuờng x y integer end Thuật toán xây