|
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; } } |