794. Valid Tic-Tac-Toe State

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters “ “, “X”, and “O”. The “ “ character represents an empty square.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (“ “).
• The first player always places “X” characters, while the second player always places “O” characters.
• “X” and “O” characters are always placed into empty squares, never filled ones.
• The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

class Solution {
public:
    bool validTicTacToe(vector<string>& board) {
        int p1 = 0, p2 =0;
        int p1cnt = 0, p2cnt = 0;
        int dx[4] {1, 1, 0, 1}, dy[4] {0, 1, 1, -1};
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++) {
                switch (board[i][j]) {
                    case 'X': p1++; break;
                    case 'O': p2++; break;
                }
                if(board[i][j] == ' ') continue;
                for(int k = 0; k < 4; k++) {
                    for(int l = 0; l < 3; l++) {
                        int nx = j + l * dx[k], ny = i + l * dy[k];
                        if(0 > nx || nx > 2 || ny < 0 || ny > 2 || board[i][j] != board[ny][nx]) break;
                        if(l == 2){
                            switch (board[i][j]) {
                                case 'X': p1cnt++; break;
                                case 'O': p2cnt++; break;
                            }
                        }
                    }
                }
            }
        return !(p2 > p1 || p1 > p2 + 1) && ((p1cnt <= 2 && p2cnt == 0 && p1 > p2) || (p2cnt <= 2 && p1cnt == 0 && p1 == p2));
    }
};