[LeetCode] Design Tic-Tac-Toe

348. Design Tic-Tac-Toe

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

  1. A move is guaranteed to be valid and is placed on an empty block.
  2. Once a winning condition is reached, no more moves are allowed.
  3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

  • TicTacToe(int n) Initializes the object the size of the board n.
  • int move(int row, int col, int player) Indicates that player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

Follow up:
Could you do better than O(n2) per move() operation?

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 {
vector<int> horizon;
vector<int> vertical;
int leftTop, rightTop, n;
bool isHorizontalWin(int row, int player) {
return horizon[row] == player * n;
}
bool isVerticalWin(int col, int player) {
return vertical[col] == player * n;
}
bool isDiagonalWin(int row, int col, int player) {
if(row == col && (row * 2 + 1) == n) return leftTopToRightDown(player) || rightTopToLeftDown(player);
return row == col ? leftTopToRightDown(player) : row + col + 1 == n ? rightTopToLeftDown(player) : false;
}
bool leftTopToRightDown(int player) {
return leftTop == player * n;
}
bool rightTopToLeftDown(int player) {
return rightTop == player * n;
}
bool isWin(int row, int col, int player) {
return isHorizontalWin(row, player) || isVerticalWin(col, player) || isDiagonalWin(row, col, player);
}
public:
/** Initialize your data structure here. */
TicTacToe(int n) : n(n), leftTop(0), rightTop(0) {
horizon = vector<int>(n,0);
vertical = vector<int>(n,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. */
int move(int row, int col, int player) {
horizon[row] += player == 2 ? -1 : 1;
vertical[col] += player == 2 ? -1 : 1;
if(row == col) leftTop += player == 2 ? -1 : 1;
if(row + col + 1 == n) rightTop += player == 2 ? -1 : 1;
return isWin(row, col, player == 2 ? -1 : 1) ? player : 0;
}
};

/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe* obj = new TicTacToe(n);
* int param_1 = obj->move(row,col,player);
*/
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/05/15/PS/LeetCode/design-tic-tac-toe/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.