05 August 2008
3x3井字棋游戏(二维数组)里面返回胜利者A或者B
检查rows, cols和对角线
1
2
3
4
5
6
7
8
9
10
11
12
13
public String tictactoe(int[][] moves) {
int[] aRow = new int[3], aCol = new int[3], bRow = new int[3], bCol = new int[3];
int aD1 = 0, aD2 = 0, bD1 = 0, bD2 = 0;
for (int i = 0; i < moves.length; ++i) {
int r = moves[i][0], c = moves[i][1];
if (i % 2 == 1) {
if (++bRow[r] == 3 || ++bCol[c] == 3 || r == c && ++bD1 == 3 || r + c == 2 && ++bD2 == 3) return "B";
}else {
if (++aRow[r] == 3 || ++aCol[c] == 3 || r == c && ++aD1 == 3 || r + c == 2 && ++aD2 == 3) return "A";
}
}
return moves.length == 9 ? "Draw" : "Pending";
}
扩展到nxn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
int n = 3;
public String tictactoe(int[][] moves) {
char[][] board = new char[n][n];
for(int i = 0; i < moves.length; i++){
int row = moves[i][0];
int col = moves[i][1];
if((i & 1) == 0){
//even, X's move
board[row][col] = 'X';
if(didWin(board, row, col, 'X')) return "A";
}else{
//odd, O's move
board[row][col] = 'O';
if(didWin(board, row, col, 'O')) return "B";
}
}
return moves.length == n * n ? "Draw" : "Pending";
}
private boolean didWin(char[][] board, int row, int col, char player){
//check the current row
boolean didPlayerWin = true;
for(int i = 0; i < n; i++){
if(board[row][i] != player){
didPlayerWin = false;
}
}
if(didPlayerWin) return true; //player has won the game
//check the current col
didPlayerWin = true;
for(int i = 0; i < n; i++){
if(board[i][col] != player){
didPlayerWin = false;
}
}
if(didPlayerWin) return true; //player has won the game
//check the diagonal
if(row == col){
didPlayerWin = true;
for(int i = 0; i < n; i++){
if(board[i][i] != player){
didPlayerWin = false;
}
}
if(didPlayerWin) return true; //player has won the game
}
//check reverse diagonal
if(col == n - row - 1){
didPlayerWin = true;
for(int i = 0; i < n; i++){
if(board[i][n-i-1] != player){
didPlayerWin = false;
}
}
if(didPlayerWin) return true; //player has won the game
}
//player did not win
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public String tictactoe(int[][] moves) {
int n = 3;
int[] rows = new int[n];
int[] cols = new int[n];
int diag1 = 0;
int diag2 = 0;
int currPlayer = 1; // 1 is 'A', -1 is 'B'
for (int[] currMove : moves) {
rows[currMove[0]] += currPlayer;
cols[currMove[1]] += currPlayer;
diag1 = currMove[0] == currMove[1] ? diag1 + currPlayer : diag1;
diag2 = currMove[0] + currMove[1] == n - 1 ? diag2 + currPlayer : diag2;
if (Math.abs(rows[currMove[0]]) == n || Math.abs(cols[currMove[1]]) == n || Math.abs(diag1) == n || Math.abs(diag2) == n) {
return currPlayer == 1 ? "A" : "B";
}
currPlayer *= -1;
}
return moves.length < 9 ? "Pending" : "Draw";
}
}