... Mỗi quân cờ domino đặt lên bàn cờ sẽ phủ kín được đúng 2 ô của bàn
cờ. Đặt lên bàn cờ 2 con tốt ở 2 ô ở 2 góc đối diện của bàn cờ. Hỏi có
thể phủ kín các ô còn lại của bàn cờ bởi các quân cờ domino sao cho
không có quân cờ nào bị chờm ra ngoài bàn cờ, không có 2 quân cờ nào đè
lên nhau hay không? Câu trả lời như đã biết là không thể được. Tuy
nhiên khi số con tốt không nhất thiết là 2 thì phụ thuộc vào phân bố
của chúng trên bàn cờ, bài toán phủ có thể có lời giải. Bài toán cần
giải khi đó là đếm xem có bao nhiêu cách phủ khác nhau.
Dữ liệu vào: từ tập tin văn bản
- Gồm 8 dòng, mỗi dòng có 8 ký tự, trong đó ký tự ‘.' để dùng chỉ ô trống, ký tự ‘#' để chỉ ô có đặt con tốt.
Dữ liệu ra: lưu vào tập tin văn bản
- Số lượng cách phủ tìm được.
Giới hạn dữ liệu:
- Số lượng quân tốt không vượt quá 63.
Ví dụ:
DOMCOVER.INP |
DOMCOVER.OUT |
#................
.................. ..................
..................
..................
..................
..................
..................# |
0 |
Hướng dẫn giải:
- Vấn
đề đặt ra là cần phủ kín những ô trống trên bàn cờ bằng những quân cờ
domino có kích thước 1x2. Do đó ta thấy có thể giải quyết bài toán bằng
phương pháp quay lui vét cạn, tại mỗi ô trống chưa được phủ trên bàn
cờ, ta xét 2 cách đặt quân cờ domino lên: đặt ngang hoặc đặt dọc, với
mỗi cách đặt xét tiếp các ô chưa được phủ tiếp theo. Mỗi khi đạt được
trạng thái cuối (toàn bộ bàn cờ được phủ kín), số lượng cách đặt được
tăng lên 1. Bài toán được giải quyết khi quá trình vét cạn hoàn tất.
- Tuy
nhiên khi sử dụng phương pháp trên, độ phức tạp tính toán là một hàm
mũ, có thể lên khá cao trong trường hợp có quá nhiều ô trống trên bàn
cờ ban đầu. Do đó ta cần thêm 1 cải tiến nhỏ để thuật toán tốt hơn.
- Dựa
trên ý tưởng vét cạn: vét cạn cho toàn bộ bàn cờ dẫn đến độ phức tạp
quá lớn, nên ta chia bàn cờ thành 2 phần, vét cạn cho mỗi phần rồi khớp
2 phần lại với nhau. Số lượng cách sắp phủ kín cả bàn cờ là tích của số
lượng cách sắp phủ kín phần 1 và số lượng cách sắp phủ kín phần 2.
Theo ity
"Kho thông tin đầy đủ nhất về dịch vụ WEB HOSTING - SERVER HOSTING" www.hosting.net.vn