Kiểm tra sau ván cờ
Đề bài
Mô tả
Câu lạc bộ cờ bàn của trường bạn vừa tổ chức một giải cờ đam (Checkers), và bạn được giao ghi chép các ván đấu. Không may, trên đường về nhà bạn đánh rơi toàn bộ giấy tờ xuống một vũng nước! Phần lớn những gì bạn viết giờ không đọc được nữa; tất cả những gì còn lại là vài danh sách các nước đi được chơi ở giữa một số ván. Liệu có cách nào dựng lại những gì đã xảy ra trong các ván đó không? Bạn phải sửa chữa thật nhanh, nếu không bạn sẽ bị giáng xuống làm người ghi chép cờ ca-rô!
Cờ đam (Checkers, hay English Draughts) là một trò chơi quen thuộc với luật đơn giản. Trò chơi diễn ra trên các ô tối của một bàn cờ . Có hai người chơi, Đen và Trắng, lần lượt thay phiên nhau di chuyển quân của mình (mọi quân của Đen màu đen, mọi quân của Trắng màu trắng). Mỗi quân chiếm một ô tối, và có thể là một quân thường hoặc một quân vua (đã được phong). Đen ngồi ở phía trên bàn cờ, Trắng ở phía dưới. Một lượt đi gồm việc chọn một quân và di chuyển nó theo một trong hai cách:
- Đi thường: dịch quân theo đường chéo sang một ô tối kề bên đang trống. Nếu là quân thường, nó chỉ được đi theo hai hướng chéo tiến về phía đối phương (đi xuống dưới với Đen, đi lên trên với Trắng). Nếu là quân vua, nó được đi theo cả bốn hướng chéo.
- Nhảy: nhảy qua một quân đối phương ở ô chéo kề bên để đến ô ngay phía bên kia (ô này phải trống), rồi bỏ quân bị nhảy qua ra khỏi bàn cờ (ăn quân đó). Quân thường chỉ được nhảy theo hai hướng đã nói ở trên, quân vua được nhảy theo cả bốn hướng. Sau đó người chơi có thể lặp lại bước này, tiếp tục nhảy bằng cùng một quân chừng nào còn quân đối phương ở vị trí thích hợp để ăn. Một chuỗi gồm một hay nhiều bước nhảy như vậy gọi là một nước nhảy.
Trong cờ đam, ăn quân là bắt buộc. Nếu đầu lượt của một người chơi có thể thực hiện một nước nhảy, người đó buộc phải nhảy, và không được dừng nhảy với quân đó cho đến khi quân đó không còn bước nhảy nào nữa. Người chơi được tự do chọn quân nào để nhảy và nhảy theo đường nào nếu có nhiều khả năng.
Nếu một quân thường đi tới hàng xa nhất tính từ phía người chơi của nó (tức là quân thường màu đen tới hàng dưới cùng, hoặc quân thường màu trắng tới hàng trên cùng), nó được thay bằng một quân vua cùng màu (được phong vua), và lượt đi kết thúc ngay. Một quân không thể vừa được phong vua rồi nhảy lùi như một quân vua mới trong cùng một lượt.
Các ô tối được đánh số từ đến như hình dưới (Đen ở phía trên, Trắng ở phía dưới; ô có số là ô tối):
grid - 1 - 2 - 3 - 4 5 - 6 - 7 - 8 - - 9 - 10 - 11 - 12 13 - 14 - 15 - 16 - - 17 - 18 - 19 - 20 21 - 22 - 23 - 24 - - 25 - 26 - 27 - 28 29 - 30 - 31 - 32 -
Cho một danh sách các nước đi, hãy tìm một thế cờ (cách bày quân) sao cho từ thế cờ đó có thể chơi hợp lệ lần lượt các nước đi trong danh sách. Thế cờ này không được có quân thường màu đen ở hàng dưới cùng hay quân thường màu trắng ở hàng trên cùng, vì những quân đó lẽ ra đã được phong vua. Bạn chỉ cần đảm bảo tuân thủ các luật nêu trên; không cần đảm bảo thế cờ này có thể đạt được trong một ván cờ đam thật.
Dữ liệu vào
Dòng đầu tiên chứa một ký tự và một số nguyên , trong đó B, W cho biết người đi nước đầu tiên (B là Đen, W là Trắng) và là số nước đi trong danh sách. Tiếp theo là dòng, mỗi dòng mô tả một nước đi theo ký hiệu cờ đam chuẩn như sau.
Nước đi thường từ ô đến ô được viết là a-b. Nước nhảy bắt đầu ở ô và lần lượt nhảy tới các ô được viết là axb1xb2x...xbk.
Dữ liệu luôn đảm bảo có lời giải cho danh sách nước đi đã cho.
Dữ liệu ra
In ra hai bàn cờ đặt cạnh nhau (cách nhau một dấu cách), gồm dòng, mỗi dòng có hai chuỗi độ dài : bàn cờ bên trái là vị trí của mọi quân trước các nước đi, bàn cờ bên phải là vị trí sau các nước đi. Dùng - cho ô sáng, . cho ô tối trống, chữ thường b và w cho quân thường màu đen và màu trắng, chữ hoa B và W cho quân vua màu đen và màu trắng.
Nếu có nhiều lời giải hợp lệ, in ra lời giải nào cũng được.
Ràng buộc
B,W, .- Các số hiệu ô trong mỗi nước đi nằm trong .
- Luôn tồn tại lời giải.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| W 3 21-17 13x22x31x24 19x28 |
-b-.-.-. -b-.-.-. .-.-.-.- .-.-.-.- -.-.-.-. -.-.-.-. B-.-w-.- .-.-w-.- -.-.-W-. -.-.-.-. w-.-.-.- .-.-.-.- -.-w-w-. -.-.-.-W .-.-.-.- .-.-.-.- |
Trắng đi quân thường 21 lên 17. Đen dùng quân vua ở ô 13 nhảy qua 17, 26, 27 tới 22, 31, rồi 24 (bước cuối nhảy lùi nên phải là vua); sau đó quân này không còn bước nhảy nào. Trắng dùng quân vua ở ô 19 nhảy lùi qua 24, ăn quân vua đen. Quân ở ô 1 và ô 15 không tham gia nước đi nào. |
| B 5 2-7 9x2 32-27 2x11x18 5-9 |
-.-b-.-W -.-.-.-W b-b-.-.- .-.-.-.- -w-.-.-. -b-.-.-. B-w-b-.- B-w-.-.- -.-.-.-. -.-W-.-. .-.-.-.- .-.-.-.- -.-.-.-. -.-.-B-. .-.-.-B- .-.-.-.- |
Quân thường trắng ở ô 9 nhảy qua 6 tới ô 2 ở hàng trên cùng: nó được phong vua và lượt kết thúc. Ở nước thứ tư, quân vua trắng mới này nhảy qua 7 và 15. |
Bình luận