Đặt các quân Hậu để chúng quản lý tất cả các ô trên bàn cờ

[rocketboy]

Bác nào có thuật toán bài này ko: Sắp xếp k<=n quân hậu trên bàn cờ nxn sao cho chúng kiểm soát tất cả các ô của bàn cờ, đơn giản cho trường hợp 8x8. Giúp mình với! Thank!

[qvluom]

n lớn nhất là bao nhiêu. Nếu nhỏ thì dùng tô màu đồ thị là hay nhất. Bạn cho mỗi ô là một đỉnh của đồ thị và xét bậc của chúng (bậc của đồ thị là số ô mà nó có thể ăn được). Ưu tiên từ cao đến thấp (mỗi lần tô màu đỉnh ta phải tính bậc lại (cũng nhanh thôi). Bạn dùng mảng một chiều có kích thước 1..n*n là được. Bài này cho kết quả tối ưu khoảng 80%. Trong trường hợp tệ nhất thì cũng sai lệnh 1 là cùng.

[rocketboy]

cám ơn bạn, đó là bài toán tổng quát, mình chỉ hỏi thuật toán để tham khảo. để đơn zản, chỉ zải cho bàn cờ vua 8x8 ô. mình biết kmin=5, nên k sẽ thuộc 5->8.

[tin_truc22]

Đệ quy quay lui cha ơi. Làm tới 8 ô mà xài đồ thị hả trời. Thời gian code còn lâu hơn thời gian đặt = tay nữa =)).

[meotrang7x]

Bác nào có thuật toán bài này ko: Sắp xếp k<=n quân hậu trên bàn cờ nxn sao cho chúng kiểm soát tất cả các ô của bàn cờ, đơn giản cho trường hợp 8x8. Giúp mình với! Thank!

Nếu k<=n thì chọn k=n luôn (vẫn thỏa mãn yêu cầu), rồi để mỗi hàng (hay mỗi cột cũng được, tùy) một quân hậu, lúc đó chúng sẽ kiểm soát tất cả bàn cờ.

[tao_may_star_94]

các pác ơi em sắp thi học sinh giỏi rồi ai có bài giả về dwowngf đi dài nhất thì post lên diễn đàn dùm em cái
sắp đến ngày tử hình rùi các bác ơi mau lên nha.
em mong tin cac pác đó

[=========> Bổ sung bài viết <=========]

pác có câu hay nhẩy bác làm pài giúp em nha

[=========> Bổ sung bài viết <=========]

Các bác ơi em sắp thi học sinh giỏi rùi mong các pác post giúp em pài về đường đi dài nhất với em cầu xin các pác đấy em sắp toi rùi nhanh lên các pác nhé