TopCoder Forums

Fri, Feb 24, 2012 at 7:17 PM EST

Help on DIV2 - 500, | Reply

jacksuyu
172 posts

I tried to use game solution, but it fails on the second test case. I couldn't figure out what's wrong. Here is the code:

public class EllysCheckers {
int N;
int state[];

public String getWinner(String board) {
N = board.length();
char[] bArr = board.toCharArray();

state = new int[getIndex(bArr) + 1];
/* state saves who win, 1 or 2.If 0 means undetermined */
return isWin(bArr, 1) ? "YES" : "NO";
}

int getIndex(char board[]) {
board[N - 1] = '.';

int v = 0;
for (int i = 0; i < N; i++) {
if (board[i] == 'o') {
v |= 1 << (N - 1 - i);
}
}

return v;
}

boolean isWin(char board[], int player) {
int nextPlayer = (player + 1) % 2 + 1;
int currIdx = getIndex(board);
if (state[currIdx] != 0) {
return state[currIdx] == player;
}

for (int i = 0; i <= 40; i++) {
int move[] = nextMove(board, i);
if (move == null) {
state[currIdx] = nextPlayer;
return false;
} else {
int type = move[0];
int idx = move[1];
boolean win = false;
if (type == 0) {
board[idx + 1] = 'o';
board[idx] = '.';
win = !isWin(board, nextPlayer);
board[idx] = 'o';
board[idx + 1] = '.';
} else if (type == 1) {
board[idx + 3] = 'o';
board[idx] = '.';
win = !isWin(board, nextPlayer);
board[idx] = 'o';
board[idx + 3] = '.';
}
if (win) {
state[currIdx] = player;
return true;
}
}
}
state[currIdx] = nextPlayer;
return false;
}

int[] nextMove(char board[], int order) {
board[N - 1] = '.';
int idx = 0;
for (int i = 0; i < board.length - 1; i++) {
if (board[i] == 'o' && board[i + 1] == '.') {
if (order == idx) {
return new int[] { 0, i };
}
idx++;
}
}
for (int i = 0; i < board.length - 3; i++) {
if (board[i] == 'o' && board[i + 1] == 'o' && board[i + 2] == 'o'
&& board[i + 3] == '.') {
if (order == idx) {
return new int[] { 1, i };
}
idx++;
}
}
return null;
}
}

Member Search