0348. Design Tic-Tac-Toe

https://leetcode.com/problems/design-tic-tac-toe

Description

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 the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

Example 1:

**Input**
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
**Output**
[null, 0, 0, 0, 0, 0, 0, 1]
**Explanation**
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is "X" and player 2 is "O" in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |
ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |
ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|
ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|
ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|
ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|
ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Constraints:

• 2 <= n <= 100

• player is 1 or 2.

• 0 <= row, col < n

• (row, col) are unique for each different call to move.

• At most n2 calls will be made to move.

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

ac

class TicTacToe {
    private int[] r1, r2, c1, c2, d1, d2;
    private int n;
    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        this.n = n;
        r1 = new int[n];
        r2 = new int[n];
        c1 = new int[n];
        c2 = new int[n];
        d1 = new int[2];
        d2 = new int[2];
    }

    /** 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) {
        // compute slope
        double mid = (n - 1) / 2.0;
        double slope = col == mid ? Double.MAX_VALUE : (row - mid) / (col - mid);


        if (player == 1) {
            r1[row]++;
            c1[col]++;

            if (slope == 1) {
                d1[0]++;
            } else if (slope == -1) {
                d1[1]++;
            } else if (row == mid && col == mid) {
                d1[0]++;
                d1[1]++;
            }
            if (r1[row] == n || c1[col] == n || d1[0] == n || d1[1] == n) return 1;
        } else {
            r2[row]++;
            c2[col]++;

            if (slope == 1) {
                d2[0]++;
            } else if (slope == -1) {
                d2[1]++;
            } else if (row == mid && col == mid) {
                d2[0]++;
                d2[1]++;
            }

            if (r2[row] == n || c2[col] == n || d2[0] == n || d2[1] == n) return 2;
        }
        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);
 */