Tic-Tac-Toe-Tomek là một trò chơi được chơi trên bảng vuông kích thước \(4 \times 4\). Ban đầu bảng trống, ngoại trừ một ký hiệu 'T' duy nhất có thể xuất hiện ở một trong 16 ô vuông. Có hai người chơi: X và O. Họ thay phiên nhau thực hiện các nước đi, bắt đầu từ X. Trong mỗi nước đi, một người chơi đặt ký hiệu của mình vào một trong các ô trống. Ký hiệu của người chơi X là 'X', và ký hiệu của người chơi O là 'O'.

Sau nước đi của một người chơi, nếu có một hàng, một cột hoặc một đường chéo chứa 4 ký hiệu của người chơi đó, hoặc chứa 3 ký hiệu của người đó và ký hiệu 'T', người đó thắng và trò chơi kết thúc. Nếu không, trò chơi tiếp tục với nước đi của người chơi kia. Nếu tất cả các ô đã được lấp đầy bởi các ký hiệu và không ai thắng, trò chơi kết thúc với kết quả hòa. Xem dữ liệu mẫu để biết ví dụ về các vị trí thắng khác nhau.

Cho mô tả bảng \(4 \times 4\) chứa các ký tự 'X', 'O', 'T' và '.' (trong đó '.' đại diện cho một ô trống), mô tả trạng thái hiện tại của một trò chơi, hãy xác định trạng thái của trò chơi Tic-Tac-Toe-Tomek đang diễn ra. Các trạng thái để lựa chọn là:

• "X won" (trò chơi đã kết thúc và X thắng)
• "O won" (trò chơi đã kết thúc và O thắng)
• "Draw" (trò chơi đã kết thúc và kết quả hòa)
• "Game has not completed" (trò chơi chưa kết thúc)

Nếu có các ô trống và trò chơi chưa kết thúc, bạn nên xuất ra "Game has not completed", ngay cả khi kết quả của trò chơi là không thể tránh khỏi.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, T. T bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm gồm 4 dòng, mỗi dòng có 4 ký tự, mỗi ký tự là 'X', 'O', '.' hoặc 'T' (dấu ngoặc kép chỉ để làm rõ). Mỗi bộ thử nghiệm được theo sau bởi một dòng trống.

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất ra một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là một trong các trạng thái được đưa ra ở trên. Hãy đảm bảo ghi đúng các trạng thái một cách chính xác. Khi bạn chạy mã của mình trên dữ liệu mẫu, nó sẽ tạo ra kết quả mẫu chính xác, bao gồm cả "Case #1: ", chữ cái viết hoa "O" thay vì số "0", v.v.

Ràng buộc

• Bảng trò chơi được cung cấp sẽ đại diện cho một trạng thái hợp lệ đạt được thông qua quá trình chơi trò chơi Tic-Tac-Toe-Tomek như mô tả ở trên.

Phân nhóm

• Small dataset (Test set 1 - Visible): \(1 \le \mathbf{T} \le 10\).
• Large dataset (Test set 2 - Hidden): \(1 \le \mathbf{T} \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

6
XXXT
....
OO..
....

XOXT
XXOO
OXOX
XXOO

XOX.
OX..
....
....

OOXX
OXXX
OX.T
O..O

XXXO
..O.
.O..
T...

OXXX
XO..
..O.
...O

Case #1: X won
Case #2: Draw
Case #3: Game has not completed
Case #4: O won
Case #5: O won
Case #6: O won

Nguồn

Google Code Jam 2013, Vòng loại, bài Tic-Tac-Toe-Tomek.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.