提示给的太直白了。。
比如player 1占据了（0,1），那么row[0]++ col[1]++
表示第一行有1个O，第一列有1个X，假设PLAYER 1最终在第一行连成一排，那最终row[0] == n。
player 2占据了(0,2)，那么 row[0]-- col[2]--
如果PLAYER最终在第三列连成一排，那么col[2] == -n
总之选手A，走到(a,b) 那个格所在行列+1，如果是对角线对角线+1，B的话就-1，先到N的就赢了。。。
public class TicTacToe
{
int[] rows;
int[] cols;
int d1;
int d2;
int n;
/** Initialize your data structure here. */
public TicTacToe(int n)
{
this.n = n;
rows = new int[n];
cols = 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 p = 0;
if(player == 1) p = 1;
else p = -1;
rows[row] += p;
if(rows[row] == n || rows[row] == -n) return player;
cols[col] += p;
if(cols[col] == n || cols[col] == -n) return player;
if(row == col)
{
d1 += p;
if(d1 == n || d1 == -n) return player;
}
if(row+col == n-1)
{
d2 += p;
if(d2 == n || d2 == -n) return player;
}
return 0;
}
}
没看提示前上头了啊。。和打DOTA一个德性。。
一开始那个办法太难了，非要做对，做了好久，提示的办法10分钟就搞定了，次奥。。
贴个一开始的办法。。
用x*n + y当做KEY，PLAYER当做VALUE来建立MAP。。
然后每次查MAP看有没有人赢。。检查MAP的时候要以当前点为中点，横纵坐标分别各从-N到+N，对角线同时-N到+N，然后一个-N到+N，一个+N到-N。
好蠢……
public class TicTacToe
{
Map<Integer,Integer> map;
int n;
/** Initialize your data structure here. */
public TicTacToe(int n)
{
this.n = n;
map = new HashMap<Integer,Integer>();
}
/** 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 key = row*n+col;
map.put(key,player);
if(check(key,player)) return player;
else return 0;
}
public boolean check(int k,int p)
{
// horizontal
int i = 0;
int row = k/n;
int col = k%n;
boolean[] check = new boolean[n];
int c = n-1;
for(int j = -c; j <= c; j++)
{
int key = (row+j)*n + col;
if(row+j < 0 || row + j >= n) i = 0;
else if(map.containsKey(key) && map.get(key) == p)
{
check[i++] = true;
if(i == n)
{
boolean temp = true;
for(int m = 0; m < n;m++)
{
temp = temp&&check[m];
if(!temp) break;
}
if(temp) return true;
}
}
else i = 0;
}
i = 0;
for(int j = -c; j <= c; j++)
{
int key = row*n + col+j;
if(col+j < 0 || col + j >= n) i = 0;
else if(map.containsKey(key) && map.get(key) == p)
{
check[i++] = true;
if(i == n)
{
boolean temp = true;
for(int m = 0; m < n;m++)
{
temp = temp&&check[m];
if(!temp) break;
}
if(temp) return true;
}
}
else i = 0;
}
i = 0;
for(int j = -c; j <= c; j++)
{
int key = (row+j)*n + col-j;
if(row + j < 0 || col-j < 0 || row + j >= n || col -j >= n) i = 0;
else if(map.containsKey(key) && map.get(key) == p)
{
check[i++] = true;
if(i == n)
{
boolean temp = true;
for(int m = 0; m < n;m++)
{
temp = temp&&check[m];
if(!temp) break;
}
if(temp) return true;
}
}
else i = 0;
}
i = 0;
for(int j = -c; j <= c; j++)
{
int key = (row-j)*n + col-j;
if(row - j < 0 || col-j < 0 || row - j >= n || col -j >= n) i = 0;
else if(map.containsKey(key) && map.get(key) == p)
{
check[i++] = true;
if(i == n)
{
boolean temp = true;
for(int m = 0; m < n;m++)
{
temp = temp&&check[m];
if(!temp) break;
}
if(temp) return true;
}
}
else i = 0;
}
return false;
/*
["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]]
["TicTacToe","move","move","move"]
[[2],[0,0,2],[1,1,1],[0,1,2]]
["TicTacToe","move","move","move"]
[[2],[0,1,1],[1,1,2],[1,0,1]]
*/
}
}
/**
* Your TicTacToe object will be instantiated and called as such:
* TicTacToe obj = new TicTacToe(n);
* int param_1 = obj.move(row,col,player);
*/
438MS 被100%的人干死了。。
空间CHEKC[]是N
MAP是N
早看提示就好了。