import java.io.PrintStream; import java.util.Arrays; import java.util.Scanner; /** * Solution to Tic tac Toe Counting. * * @author vanb */ public class tictactoecounting_vanb { /** Input. */ private static Scanner sc; /** Output. */ private static PrintStream ps; /** The wins. wins[0] is wins for X, wins[1] is for O */ private int wins[][]; /** The powers of three. */ private int p3[]; /** The Constant SYMBOLS - symbols for the players and empty spaces. */ private static final String SYMBOLS = ".XO"; /** The board. */ private int board[]; /** * Determine if a player has won. * * @param player the player * @param i the A cell to check * @param j the Another cell to check * @param k the Yet another cell to check * @return true, if the player has 3 in a row */ private boolean win( int player, int i, int j, int k ) { return board[i]==player && board[j]==player && board[k]==player; } /** * Count wins. * * @param key the key for the board position * @param player the player (1 for X, 2 for O) */ private void countWins( int key, int player ) { if( wins[0][key]==-1 ) { // Check to see f the opponent has won int opp = 3-player; if( win( opp, 0, 1, 2 ) || win( opp, 3, 4, 5 ) || win( opp, 6, 7, 8 ) || win( opp, 0, 3, 6 ) || win( opp, 1, 4, 7 ) || win( opp, 2, 5, 8 ) || win( opp, 0, 4, 8 ) || win( opp, 2, 4, 6 ) ) { wins[opp-1][key] = 1; wins[player-1][key] = 0; } else { wins[0][key] = 0; wins[1][key] = 0; // Otherwise make all possible remaining moves for this player for( int i=0; i<9; i++ ) if( board[i]==0 ) { board[i] = player; int newkey = key + player*p3[i]; countWins( newkey, opp ); wins[0][key] += wins[0][newkey]; wins[1][key] += wins[1][newkey]; board[i] = 0; } } } } /** * Do it!. */ private void doit() { // Initialize wins with -1s. // We'll play all possible games, so any unreached states need to be -1 wins = new int[2][20000]; Arrays.fill( wins[0], -1 ); Arrays.fill( wins[1], -1 ); // Precompute powers of 3 p3 = new int[9]; p3[0] = 1; for( int i=1; i<9; i++ ) p3[i] = 3*p3[i-1]; // Initialize the board: 0=empty, 1=X, 2=O board = new int[9]; Arrays.fill( board, 0 ); // Precompute wins[][] by counting wins from an empty board countWins( 0, 1 ); // For the input, just look up in the wins[][] array. int t = sc.nextInt(); sc.nextLine(); while( t-->0 ) { char test[] = sc.next().toCharArray(); int key = 0; for( int i=0; i