Description
Design a Tic-tac-toe game that is played between two players on a n x n grid.
You may assume the following rules:
A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves is allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example
1 | Example: |
Solution
$O(1)$ Solution1
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
40class TicTacToe {
int[] rows, cols;
int d1, d2, n;
public TicTacToe(int n) {
rows = new int[n];
cols = new int[n];
d1 = 0;
d2 = 0;
this.n = n;
}
public int move(int row, int col, int player) {
int val = (player == 1) ? 1 : -1;
int target = (player == 1) ? n : -n;
if(row == col) { // diagonal
d1 += val;
if(d1 == target) return player;
}
if(row + col + 1 == n) { // diagonal
d2 += val;
if(d2 == target) return player;
}
rows[row] += val;
cols[col] += val;
if(rows[row] == target || cols[col] == target) return player;
return 0;
}
}
/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/
$O(N)$ Solution
class TicTacToe {
int[][] board;
int bn;
/** Initialize your data structure here. */
public TicTacToe(int n) {
board = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = 0;
bn = 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) {
board[row][col] = player;
int flag = 0;
for (int i = 0; i < bn; i++){
// System.out.println(board[row][i] + " " + player);
if (board[row][i] != player){
flag = 1;
break;
}
}
// System.out.println(flag);
if (flag == 0) return player;
flag = 0;
for (int i = 0; i < bn; i++){
if (board[i][col] != player){
flag = 1;
break;
}
}
if (flag == 0) return player;
if (row - col == 0){
flag = 0;
int x = 0;
int y = 0;
for (int i = 0; i < bn; i++){
if (board[x][y] != player){
flag = 1;
break;
}
x++;
y++;
}
if (flag == 0) return player;
}
if (row + col == bn-1){
flag = 0;
int x = 0;
int y = bn-1;
for (int i = 0; i < bn; i++){
if (board[x][y] != player){
flag = 1;
break;
}
x++;
y--;
}
if (flag == 0) return player;
}
return 0;
}
}
/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/