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:
Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board. TicTacToe toe = new TicTacToe(3); toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | | // Player 1 makes a move at (0, 0).
| | | | toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 2 makes a move at (0, 2).
| | | | toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | | // Player 1 makes a move at (2, 2).
| | |X| toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 2 makes a move at (1, 1).
| | |X| toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| | // Player 1 makes a move at (2, 0).
|X| |X| toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| | // Player 2 makes a move at (1, 0).
|X| |X| toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| | // Player 1 makes a move at (2, 1).
|X|X|X|
Follow up:
Could you do better than O(n2) per move()
Hint:
Could you trade extra space such that move() operation can be done in O(1)?
You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.
CareerCup上的原题，请参见我之前的博客17.2 Tic Tac Toe。我们首先来O(n2)的解法，这种方法的思路很straightforward，就是建立一个nxn大小的board，其中0表示该位置没有棋子，1表示玩家1放的子，2表示玩家2。那么棋盘上每增加一个子，我们都扫描当前行列，对角线，和逆对角线，看看是否有三子相连的情况，有的话则返回对应的玩家，没有则返回0，参见代码如下：
解法一：
class TicTacToe {
public:
/** Initialize your data structure here. */
TicTacToe(int n) {
board.resize(n, vector<int>(n, ));
}
int move(int row, int col, int player) {
board[row][col] = player;
int i = , j = , n = board.size();
for (j = ; j < n; ++j) {
if (board[row][j] != board[row][j - ]) break;
}
if (j == n) return player;
for (i = ; i < n; ++i) {
if (board[i][col] != board[i - ][col]) break;
}
if (i == n) return player;
if (row == col) {
for (i = ; i < n; ++i) {
if (board[i][i] != board[i - ][i - ]) break;
}
if (i == n) return player;
}
if (row + col == n - ) {
for (i = ; i < n; ++i) {
if (board[n - i - ][i] != board[n - i][i - ]) break;
}
if (i == n) return player;
}
return ;
}
private:
vector<vector<int>> board;
};
Follow up中让我们用更高效的方法，那么根据提示中的，我们建立一个大小为n的一维数组rows和cols，还有变量对角线diag和逆对角线rev_diag，这种方法的思路是，如果玩家1在第一行某一列放了一个子，那么rows[0]自增1，如果玩家2在第一行某一列放了一个子，则rows[0]自减1，那么只有当rows[0]等于n或者-n的时候，表示第一行的子都是一个玩家放的，则游戏结束返回该玩家即可，其他各行各列，对角线和逆对角线都是这种思路，参见代码如下：
解法二：
class TicTacToe {
public:
/** Initialize your data structure here. */
TicTacToe(int n): rows(n), cols(n), N(n), diag(), rev_diag() {}
int move(int row, int col, int player) {
int add = player == ? : -;
rows[row] += add;
cols[col] += add;
diag += (row == col ? add : );
rev_diag += (row == N - col - ? add : );
return (abs(rows[row]) == N || abs(cols[col]) == N || abs(diag) == N || abs(rev_diag) == N) ? player : ;
}
private:
vector<int> rows, cols;
int diag, rev_diag, N;
};
参考资料：
https://leetcode.com/problems/design-tic-tac-toe/
https://discuss.leetcode.com/topic/44548/java-o-1-solution-easy-to-understand
https://discuss.leetcode.com/topic/44605/c-time-o-1-space-o-n-short-simple-solution