# 348. Design Tic-Tac-Toe

• Time: $O(1)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 class TicTacToe { public: TicTacToe(int n) : n(n), rows(n), cols(n) {} /** * Player {player} makes a move at ({row}, {col}). * * @param row The row of the board. * @param col The column of the board. * @param player The player, can be either 1 or 2. * @return The current winning condition, can be either: * 0: No one wins. * 1: Player 1 wins. * 2: Player 2 wins. */ int move(int row, int col, int player) { const int toAdd = player == 1 ? 1 : -1; const int target = player == 1 ? n : -n; if (row == col) { diag += toAdd; if (diag == target) return player; } if (row + col == n - 1) { antiDiag += toAdd; if (antiDiag == target) return player; } rows[row] += toAdd; if (rows[row] == target) return player; cols[col] += toAdd; if (cols[col] == target) return player; return 0; } private: const int n; // record count('X') - count('O') vector rows; vector cols; int diag = 0; int antiDiag = 0; }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 class TicTacToe { public TicTacToe(int n) { this.n = n; rows = new int[n]; cols = new int[n]; } /** * Player {player} makes a move at ({row}, {col}). * * @param row The row of the board. * @param col The column of the board. * @param player The player, can be either 1 or 2. * @return The current winning condition, can be either: * 0: No one wins. * 1: Player 1 wins. * 2: Player 2 wins. */ public int move(int row, int col, int player) { final int toAdd = player == 1 ? 1 : -1; final int target = player == 1 ? n : -n; if (row == col) { diag += toAdd; if (diag == target) return player; } if (row + col == n - 1) { antiDiag += toAdd; if (antiDiag == target) return player; } rows[row] += toAdd; if (rows[row] == target) return player; cols[col] += toAdd; if (cols[col] == target) return player; return 0; } private final int n; // record count('X') - count('O') private int[] rows; private int[] cols; private int diag = 0; private int antiDiag = 0; } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class TicTacToe: def __init__(self, n: int): self.n = n # record count('X') - count('O') self.rows = [0] * n self.cols = [0] * n self.diag = 0 self.antiDiag = 0 """ Player {player} makes a move at ({row}, {col}). @param row The row of the board. @param col The column of the board. @param player The player, can be either 1 or 2. @return The current winning condition, can be either: 0: No one wins. 1: Player 1 wins. 2: Player 2 wins. """ def move(self, row: int, col: int, player: int) -> int: toAdd = 1 if player == 1 else -1 target = self.n if player == 1 else -self.n if row == col: self.diag += toAdd if self.diag == target: return player if row + col == self.n - 1: self.antiDiag += toAdd if self.antiDiag == target: return player self.rows[row] += toAdd if self.rows[row] == target: return player self.cols[col] += toAdd if self.cols[col] == target: return player return 0 
Back to top