using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace TicTacToe { class Scanner { TextReader Reader; public Scanner(TextReader reader) { Reader = reader; } static int Index = 0; static string[] CurrentLine = { }; public bool HasNext() { if (CurrentLine.Length == Index) { try { CurrentLine = Reader.ReadLine().Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); Index = 0; return HasNext(); } catch (Exception e) { return false; } } return true; } public String Next() { if (HasNext()) return CurrentLine[Index++]; return null; } public int NextInt() { return int.Parse(Next()); } public long NextLong() { return long.Parse(Next()); } public float NextFloat() { return float.Parse(Next()); } public double NextDouble() { return double.Parse(Next()); } } class TicTacToe { static char[,] grid; static void Main(string[] args) { Scanner inp = new Scanner(Console.In); int cases = inp.NextInt(); for (int caseOn = 1; caseOn <= cases; caseOn++) { grid = new char[3, 3]; for (int i = 0; i < 3; i++) { string next = inp.Next(); for (int j = 0; j < 3; j++) { grid[i, j] = next[j]; } } int winner = go(); string message = "Cats Game"; if (winner == 1) message = "X wins"; if (winner == 2) message = "O wins"; Console.WriteLine(message); } } static void printGrid() { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { Console.Write(grid[i, j]); } Console.WriteLine(); } } static int go() { char player = 'X'; int play = 1; if (count('X') > count('O')) { player = 'O'; play = 2; } //printGrid(); //Console.WriteLine("Count 'X'= {0}, Count 'O' = {1}", count('X'), count('O')); //Console.WriteLine("Player is {0}", player); //Console.WriteLine(); if (Wins('X')) return 1; if (Wins('O')) return 2; if (count('X') + count('O') == 9) { return 3; } // Assume that you are going to lose. int ret = 3 - play; // If you can find a move that means you win, take it. // Otherwise if you find a tie, take that. for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { // try going here: if (grid[i, j] == '.') { grid[i, j] = player; int winner = go(); grid[i, j] = '.'; if (winner == play) { ret = play; break; } if (winner == 3) { ret = 3; // I might need to take the tie. } } } if (ret == play) break; } return ret; } static int count(char sym) { int cnt = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (grid[i, j] == sym) cnt++; } } return cnt; } static bool Wins(char sym) { for (int i = 0; i < 3; i++) { int rC = 0; int cC = 0; for (int j = 0; j < 3; j++) { if (grid[i, j] == sym) rC++; if (grid[j, i] == sym) cC++; } if (rC == 3 || cC == 3) return true; } int d1C = 0, d2C = 0; for (int i = 0; i < 3; i++) { if (grid[i, i] == sym) d1C++; if (grid[i, 2 - i] == sym) d2C++; } if (d1C == 3 || d2C == 3) return true; return false; } } }