348. Design Tic-Tac-Toe
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.
Could you do better than O(n2) per move() operation?
- 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.
一盘棋，要赢的话，要任意行，列，斜线都是相同的棋子才可以。总共有2n + 2总赢法。行数+列数+正斜线+反斜线。
用一个长为2n * 2的数组，来统计行，列，斜线的棋子出现次数。counter[0, n - 1] 统计行，counter[n, 2n - 1] 统计列，counter[2n]为正斜线，counter[2n + 1]为反斜线。player1下棋，counter + 1, player2下棋, counter - 1。