Design Tic-Tac-Toe

这道题需要一个时间复杂度低于O(n^2)的move函数，最简单的就是对新加入点的行列以及对角线进行检查，对角线检查还是利用那个对角线横纵坐标的和差的规律，这样相当于做了四次n循环，时间复杂度是O(n)，不过discussion里面好像有O(1)的算法，暂时先不研究了

class TicTacToe(object):

    def __init__(self, n):
        """
        Initialize your data structure here.
        :type n: int
        """
        self.board = [[None] * n for _ in xrange(n)]
        self.n = n

    def move(self, row, col, player):
        """
        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.
        :type row: int
        :type col: int
        :type player: int
        :rtype: int
        """
        self.board[row][col] = player
        if self.checkRow(col, player):
            return player
        if self.checkCol(row, player):
            return player
        if self.checkDia(row, col, player):
            return player
        return 0

    def checkRow(self, col, player):
        for i in xrange(self.n):
            if self.board[i][col] != player:
                return False
        return True

    def checkCol(self, row, player):
        for i in xrange(self.n):
            if self.board[row][i] != player:
                return False
        return True

    def checkDia(self, row, col, player):
        if (row + col != self.n - 1) and (row - col != 0):
            return False

        result = True
        for i in xrange(self.n):
            if self.board[i][self.n - i - 1] != player:
                result = False
                break

        if result:
            return True

        for i in xrange(self.n):
            if self.board[i][i] != player:
                return False

        return True

# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)