348. Design Tic-Tac-Toe (Medium)

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

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 is allowed.
3. 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(n^2)$$ per move() operation?

Hint:

1. Could you trade extra space such that move() operation can be done in O(1)?
2. You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.

Solution 1: Brute Force 36ms

Time Complexity: move() $$O(n)$$

Space Complexity: $$O(n^2)$$

Check current row, col; if the move is in diagonal or anti-diagonal line, also check

class TicTacToe {
public:
    /** Initialize your data structure here. */
    TicTacToe(int n) {
        n_ = n;
        board = vector<vector<int>>(n, 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) {
        board[row][col] = player;
        bool win = true;
        for (int i = 0; i < n_; ++i) {
            if (board[i][col] != player) {
                win = false;
                break;
            }
        }
        if (win) return player;
        win = true;
        for (int j = 0; j < n_; ++j) {
            if (board[row][j] != player) {
                win = false;
                break;
            }
        }
        if (win) return player;

        if (row == col) {
            win = true;
            for (int i = 0; i < n_; ++i) {
                if (board[i][i] != player) {
                    win = false;
                    break;
                }
            }
            if (win) return player;
        }

        // anti-diagonal
        if (row == n_ -col-1) {
            win = true;
            for (int i = 0; i < n_; ++i) {
                if (board[i][n_-i-1] != player) {
                    win = false;
                    break;
                }
            }
            if (win) return player;
        }
        return 0;

    }
private:
    int n_;
    vector<vector<int>> board;
};

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

Solution 2: Follow up 33ms

Time Complexity: move() $$O(1)$$

Space Complexity: $$O(n)$$

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): n_(n), diagonal(0), anti_diagonal(0), rows(n,0), cols(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) {
        int add = (player == 1) ? 1:-1;
        rows[row] += add;
        cols[col] += add;
        if (row == col) diagonal += add;
        if (row == n_-col-1) anti_diagonal += add;

        return (abs(rows[row]) == n_ || abs(cols[col]) == n_ || abs(diagonal) == n_ || abs(anti_diagonal) == n_) ? player:0;

    }
private:
    int n_, diagonal, anti_diagonal;
    vector<int> rows, cols;
};

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */