Nước cờ chiến thắng
Đề bài
Mô tả
Hai người chơi cờ ca-rô trên bảng . Người thứ nhất đi trước và luôn đánh dấu X, người thứ hai đánh dấu O. Người chiến thắng là người đầu tiên tạo được ba dấu của mình nằm liền kề nhau trên một hàng ngang, một cột dọc, hoặc một đường chéo.
Ván đấu đang dở dang và đến lượt người chơi X đi. Cho trạng thái hiện tại của bảng (đảm bảo là một trạng thái hợp lệ và ván chưa kết thúc). Hãy xác định xem người chơi X có thể thắng ngay bằng đúng một nước đi hay không, tức là có tồn tại một ô trống mà khi đặt X vào đó sẽ tạo được ba dấu X liền kề nhau trên một đường thẳng (ngang, dọc, hoặc chéo).
Dữ liệu vào
Gồm dòng, mỗi dòng gồm ký tự mô tả một hàng của bảng. Mỗi ký tự là một trong:
- dấu chấm
.biểu diễn ô trống, - chữ
xbiểu diễn dấu X, - chữ
obiểu diễn dấu O.
Dữ liệu ra
In ra YES nếu người chơi X có thể thắng chỉ bằng một nước đi, ngược lại in ra NO.
Ràng buộc
- Bảng có kích thước .
- Trạng thái đầu vào luôn hợp lệ và ván chưa kết thúc (chưa có ba dấu liền kề của bất kỳ người chơi nào).
- Bảng có thể hoàn toàn trống, nghĩa là hai người rời đi mà chưa đánh dấu nào.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| xx.. .oo. x... oox. |
YES | Đặt X vào ô trống thứ ba của hàng đầu tạo thành ba dấu X liền kề xx x trên hàng ngang. |
| x.ox ox.. x.o. oo.x |
NO | Không có nước đi nào tạo được ba dấu X liền kề. |
| x..x ..oo o... x.xo |
YES | Đặt X vào ô giữa của hàng cuối để có ba dấu X liền kề trên hàng ngang. |
| .... .... .... .... |
NO | Bảng trống, đặt một dấu X không thể tạo được ba dấu liền kề. |
Bình luận