#include #include #include #include using namespace std; bool DEBUG = true; // make this a DP problem // key for lookup is a string representation of the board // stored is the count of X wins and O wins map > dp; void print_board(string board) { for (int i = 0; i < 9; i++) { cout << board[i]; if (i == 2 || i == 5 || i == 8) cout << endl; } } // given the current turn, return who is making the next turn char next_turn(char turn) { if (turn == 'X') return 'O'; return 'X'; } // given a valid game, determine the winner // (yes, there's probably a better way to do this) char check_game(string board) { // board is a single string // indexes in the 2-d version map in this way: // | 0 1 2 // ----|------------ // 0 | 0 1 2 // 1 | 3 4 5 // 2 | 6 7 8 // win in row for (int r = 0; r < 3; r++) { if (board[r*3] == board[r*3+1] && board[r*3+1] == board[r*3+2] && board[r*3] != '.') return board[r*3]; } // win in column for (int c = 0; c < 3; c++) { if (board[c] == board[c+3] && board[c+3] == board[c+6] && board[c] != '.') return board[c]; } // win on diagonal if (board[0] == board[4] && board[4] == board[8] && board[0] != '.') return board[0]; if (board[2] == board[4] && board[4] == board[6] && board[2] != '.') return board[2]; return '.'; } // use dynamic programming (with recursion) to solve the problem pair solve_problem(string board, char turn) { // check the dp table - if we've already computed // result for this board, return stored solution if (dp.find(board) != dp.end()) { return dp[board]; } // no stored solution, must compute it int x_total = 0; int o_total = 0; pair result; bool finished = false; // if someone has won the game, // return the corresponding win counts char winner = check_game(board); // X wins if (winner == 'X') { result = make_pair(1, 0); finished = true; } // Y wins else if (winner == 'O') { result = make_pair(0, 1); finished = true; } // board is full, but no winner - tie else if (board.find('.') == std::string::npos) { result = make_pair(0, 0); finished = true; } if (finished) { //save result so we don't have to check this board again dp[board] = result; return result; } // try putting next move in all empty board positions for (int i = 0; i < 9; i++) { if (board[i] == '.') { board[i] = turn; result = solve_problem(board, next_turn(turn)); x_total += result.first; o_total += result.second; // set back to empty board[i] = '.'; } } // store result for this board state dp[board] = make_pair(x_total, o_total); // return solution return dp[board]; } int main() { int t; // number of cases // precompute all the answers // dp table is at the top (global) // start from an empty board, play the game, // and save all the results string board = "........."; solve_problem(board, 'X'); // now, answer the queries cin >> t; for (int case_num = 0; case_num < t; case_num++) { cin >> board; // read board as a single string // lookup answer from table and print if (dp.find(board) == dp.end()) cout << -1 << " " << -1 << endl; else cout << dp[board].first << " " << dp[board].second << endl; } }