請在 n ×?n 的棋盤上，實現一個判定井字棋（Tic-Tac-Toe）勝負的神器，判斷每一次玩家落子后，是否有勝出的玩家。
在這個井字棋游戲中，會有 2 名玩家，他們將輪流在棋盤上放置自己的棋子。
在實現這個判定器的過程中，你可以假設以下這些規則一定成立：
??????1. 每一步棋都是在棋盤內的，并且只能被放置在一個空的格子里；
??????2. 一旦游戲中有一名玩家勝出的話，游戲將不能再繼續；
??????3. 一個玩家如果在同一行、同一列或者同一斜對角線上都放置了自己的棋子，那么他便獲得勝利。
示例:
給定棋盤邊長 n = 3, 玩家 1 的棋子符號是 "X"，玩家 2 的棋子符號是 "O"。
TicTacToe toe = new TicTacToe(3);
toe.move(0, 0, 1); -> 函數返回 0 (此時，暫時沒有玩家贏得這場對決)
|X| | |
| | | | ? ?// 玩家 1 在 (0, 0) 落子。
| | | |
toe.move(0, 2, 2); -> 函數返回 0 (暫時沒有玩家贏得本場比賽)
|X| |O|
| | | | ? ?// 玩家 2 在 (0, 2) 落子。
| | | |
toe.move(2, 2, 1); -> 函數返回 0 (暫時沒有玩家贏得比賽)
|X| |O|
| | | | ? ?// 玩家 1 在 (2, 2) 落子。
| | |X|
toe.move(1, 1, 2); -> 函數返回 0 (暫沒有玩家贏得比賽)
|X| |O|
| |O| | ? ?// 玩家 2 在 (1, 1) 落子。
| | |X|
toe.move(2, 0, 1); -> 函數返回 0 (暫無玩家贏得比賽)
|X| |O|
| |O| | ? ?// 玩家 1 在 (2, 0) 落子。
|X| |X|
toe.move(1, 0, 2); -> 函數返回 0 (沒有玩家贏得比賽)
|X| |O|
|O|O| | ? ?// 玩家 2 在 (1, 0) 落子.
|X| |X|
toe.move(2, 1, 1); -> 函數返回 1 (此時，玩家 1 贏得了該場比賽)
|X| |O|
|O|O| | ? ?// 玩家 1 在 (2, 1) 落子。
|X|X|X|
?
進階:
您有沒有可能將每一步的?move()?操作優化到比?O(n2) 更快嗎?
題意因該是想每一次move都把棋盤全部檢查一遍，但是沒必要。
進階的意思：只把新move位置的所在行、列、和兩個對角線檢查一下即可，時間o(n),空間o(n*n)代碼如下。
class TicTacToe {int arr[][];/** Initialize your data structure here. */public TicTacToe(int n) {arr=new int[n][n];}/** 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) {arr[row][col]=player;if(checkCol(col,player) || checkRow(row,player) || line1(player) || line2(player)){return player;}return 0;}public boolean checkRow(int row,int player) {int len=arr.length;for(int i=0;i<len;i++){if(arr[row][i]!=player){return false;}}return true;}public boolean checkCol(int col,int player) {int len=arr.length;for(int i=0;i<len;i++){if(arr[i][col]!=player){return false;}}return true;}public boolean line1(int player){int len=arr.length;int ans=0;for(int i=0;i<len;i++){if(arr[i][i]!=player){return false;}}return true;}public boolean line2(int player){int len=arr.length;int ans=0;for(int i=0;i<len;i++){if(arr[i][len-i-1]!=player){return false;}}return true;}}/*** Your TicTacToe object will be instantiated and called as such:* TicTacToe obj = new TicTacToe(n);* int param_1 = obj.move(row,col,player);*/更好的思路，把每一行每一列，和兩個對角線的情況記錄下來，玩家1使所在行列對角線-1，玩家1使所在行列對角線+1.
只有某個數等于n或-n時，某個玩家會獲勝。
class TicTacToe {int rowArr[];int colArr[];int line1=0;int line2=0;/** Initialize your data structure here. */public TicTacToe(int n) {rowArr=new int[n];colArr=new int[n];}/** 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) {int n=rowArr.length;int temp=player==1?-1:1;rowArr[row]+=temp;colArr[col]+=temp;if(row==col){line1+=temp;}if(col==n-row-1){line2+=temp;}if(rowArr[row]==n || colArr[col]==n || rowArr[row]==-n || colArr[col]==-n || line1==n || line2==n || line1==-n || line2==-n){return player;}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);*/?
)
