Bài toán xếp hậu khác
Chào mọi người, em đang gặp khó khăn về bài toán này. Mọi người có thể cho em xin vài gợi ý với ạ.
ĐỀ BÀI:
Trên một bàn cờ vua kích thước 8x8 hãy đặt số lượng tối thiểu các quân hậu lên bàn cờ sao cho tất cả các ô của bàn cờ đều bị khống chế bởi ít nhất một quân hậu và các quân hậu không khống chế lẫn nhau. Một số ô trên bàn cờ đã bị hủy (không tính). Mỗi quân hậu không được đặt trên ô bị hủy và các ô này cũng không cần khống chế tuy nhiên một ô sẽ được tính là bị khống chế nếu như có một quân hậu nằm cùng hàng hoặc cột hoặc một trong các đường chéo tương ứng với ô đó. Các hàng được đánh số từ 1 đến 8 và các cột được đánh số từ ký tự ‘A’ tới ký tự ‘H’.
Input
Dữ liệu của chương trình được cho trong file text gồm 8 dòng, mỗi dòng gồm 8 ký tự, ký tự ‘.’ có nghĩa là ô trống trên bàn cờ, ký tự ‘#’ có nghĩa là ô hủy trên bàn cờ (không tính).
Output
Kết quả chương trình ghi vào file text gồm vị trí của các quân hậu thỏa mãn điều kiện đầu bài, mỗi vị trí được mô tả bằng chỉ số hàng và chỉ số cột viết liền nhau.
Ví dụ
Input
…
…######
.#.#####
.##.####
.###.###
.####.##
.#####.#
…
Output
1A8B
Thử vét cạn xem chạy nổi không sau đó cải tiến theo hướng
cái khó ở đây là tối thiểu nên nghĩ theo hướng tham để tối ưu kết quả càng sớm càng tốt, đỡ duyệt nhiều.
Vét cạn + tham: mỗi bước ưu tiên đặt con hậu sao cho nó kiểm soát được nhiều ô chưa kiểm soát nhất.
(ưu tiên nhé, vẫn vét hết)
điều kiện chặn: tại bước bất kỳ số con hậu đã dùng>= best_result-2 và không tồn tại con hậu kiểm soát hết các ô còn lại (cái này có thể làm trong 0(1))
p/s: Chuẩn bị 1 mảng 46 phần tử đại diện cho 46 đường thẳng trong bàn cờ => tính số ô kiểm soát của 1 con hậu cho nhanh
Cảm ơn bạn đã góp ý .