Trò chơi - Giả sử có n × n mảng hình vuông. Trong số này, một số ô trống, một số ô liền và một số ô không liền khối được đặt bởi các số nguyên 1, 2, 3,… .Mỗi số nguyên duy trì hoặc chiếm đúng hai ô vuông khác nhau trên bàn cờ. Nhiệm vụ của người chơi là kết nối hai lần xuất hiện của mỗi số nguyên trên bàn cờ với sự trợ giúp của một con đường đơn giản thực hiện các chuyển động ngang và dọc một mình. Không được phép có hai con đường khác nhau cắt nhau. Không có con đường nào có thể bao gồm bất kỳ hình vuông đặc nào (các hình vuông đặc không được phép xuất hiện trên bất kỳ con đường nào). Cuối cùng, tất cả các ô vuông không liền khối phải được lấp đầy bởi các đường dẫn.
Thuật toán - Để tạo một câu đố ngẫu nhiên hợp lệ với kích thước bảng đã cho là n × n, trước tiên chúng ta tạo ra các đường dẫn ngẫu nhiên đơn giản không giao nhau trên bảng. Nếu một vài hình vuông cô lập vẫn nằm ngoài tất cả các đường dẫn đã tạo, hãy đánh dấu những hình vuông cô lập này là rắn (bị cấm). Tiếp theo, chúng tôi cung cấp các điểm cuối của các đường dẫn và danh sách các hình vuông đặc làm câu đố.
Vì vậy, trước tiên chúng tôi đưa ra một giải pháp, và tiếp theo là tìm ra câu đố từ giải pháp. Các đường dẫn và các ô vuông đặc phân chia hoặc phân vùng bảng n × n. Chúng tôi triển khai cấu trúc dữ liệu tìm kiếm liên hiệp để tạo ra phân vùng này. Cấu trúc dữ liệu được xử lý với các tập con của tập hợp n ^ 2 ô vuông trên bàn cờ.
Mã giả
-
Xác định vị trí các ô vuông (a, b) và (c, d) ngẫu nhiên trên bảng sao cho -
-
(a, b) và (c, d) là hàng xóm của nhau và
-
cả (a, b) và (c, d) đều không thuộc bất kỳ con đường nào được tạo ra cho đến nay. Nếu không tìm thấy cặp ô vuông nào như vậy trên bảng trực tiếp, hãy trả về FAILURE / * Ở đây, (a, b) và (c, d) là hai ô vuông đầu tiên trên đường dẫn mới được xây dựng. * /
-
-
Tạo sự kết hợp của hai cây tìm kiếm kết hợp chứa (a, b) và (c, d).
-
Lặp lại miễn là có thể mở rộng đường dẫn hiện tại -
-
Đổi tên (a, b) =(c, d).
-
-
Định vị một hình vuông lân cận ngẫu nhiên (c, d) của (a, b) sao cho -
-
(c, d) không thuộc bất kỳ đường dẫn nào được sản xuất cho đến nay (kể cả đường dẫn hiện tại)
-
người hàng xóm duy nhất (c, d) có trên con đường hiện tại được xây dựng một phần là (a, b).
-
-
Nếu không tìm thấy hàng xóm (c, d) như vậy, đường dẫn không thể được mở rộng thêm, vì vậy hãy ngắt vòng lặp
-
Nếu không, hãy tạo sự kết hợp của hai cây tìm kết hợp mà (a, b) và (c, d) thuộc về.
-
Đặt cờ điểm cuối của hai hình vuông ở đầu và cuối của đường dẫn mới.
-
Trở lại THÀNH CÔNG