Valid|Valid Tic-Tac-Toe State
题目
A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The " " character represents an empty square.
Here are the rules of Tic-Tac-Toe:
Players take turns placing characters into empty squares (" ").
The first player always places "X" characters, while the second player always places "O" characters.
"X" and "O" characters are always placed into empty squares, never filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.
答案
Code may be a bit long because of the simple helper functions, but the main idea is REALLY straighforward:
Step 1, check #X = #O, or #X = #O + 1, otherwise it couldn't be a valid state
Step 2, recursively take off pieces until board is empty.
【Valid|Valid Tic-Tac-Toe State】If there is one way you can take pieces off without triggering the end condition, then it means there is at least one way you can start from an empty board and reach the state given.
public int countPieces(char[][] board, char piece) {
int cnt = 0;
for(int i = 0;
i < 3;
i++) {
for(int j = 0;
j < 3;
j++) {
if(board[i][j] == piece) cnt++;
}
}
return cnt;
}public boolean isEnd(char[][] board) {
// Horizontal
String s0 = Character.toString(board[0][0]) + Character.toString(board[0][1]) + Character.toString(board[0][2]);
String s1 = Character.toString(board[1][0]) + Character.toString(board[1][1]) + Character.toString(board[1][2]);
String s2 = Character.toString(board[2][0]) + Character.toString(board[2][1]) + Character.toString(board[2][2]);
// Vertical
String s3 = "", s4 = "", s5 = "";
s3 = Character.toString(board[0][0]) + Character.toString(board[1][0]) + Character.toString(board[2][0]);
s4 = Character.toString(board[0][1]) + Character.toString(board[1][1]) + Character.toString(board[2][1]);
s5 = Character.toString(board[0][2]) + Character.toString(board[1][2]) + Character.toString(board[2][2]);
// Diagonal
String s6 = "", s7 = "";
s6 = Character.toString(board[0][0]) + Character.toString(board[1][1]) + Character.toString(board[2][2]);
s7 = Character.toString(board[0][2]) + Character.toString(board[1][1]) + Character.toString(board[2][0]);
return s0.equals("XXX") || s0.equals("OOO") || s1.equals("XXX") || s1.equals("OOO") || s2.equals("XXX") ||
s2.equals("OOO") || s3.equals("XXX") || s3.equals("OOO") || s4.equals("XXX") || s4.equals("OOO") ||
s5.equals("XXX") || s5.equals("OOO") || s6.equals("XXX") || s6.equals("OOO") || s7.equals("XXX") ||
s7.equals("OOO");
}public boolean validTicTacToe(String[] board) {
// Convert array of strings to character board
char[][] cBoard = new char[3][3];
for(int i = 0;
i < 3;
i++)
for(int j = 0;
j < 3;
j++)
cBoard[i][j] = board[i].charAt(j);
// First, check either #X = #O or #X = #O + 1
int numX = countPieces(cBoard, 'X');
int numO = countPieces(cBoard, 'O');
if(numX != numO && numX != numO + 1) return false;
// Second, start with current state, find a way to remove pieces without meeting the end condition
return recur(cBoard, numX, numO, true);
}public boolean recur(char[][] board, int numX, int numO, boolean start) {
if(numX == 0 && numO == 0) return true;
if(isEnd(board) && !start) return false;
boolean turn = numX > numO;
boolean ret = false;
// If to take 'X' off, recur on the choices of X. Same logic for 'O'.for(int i = 0;
i < 3;
i++) {
for(int j = 0;
j < 3;
j++) {
if(turn && board[i][j]== 'X') {
// Set board[i][j] to empty
board[i][j] = ' ';
ret = ret || recur(board, numX - 1, numO, false);
// Restore board
board[i][j] = 'X';
}
else if(!turn && board[i][j] == 'O') {
// Set board[i][j] to empty
board[i][j] = ' ';
ret = ret || recur(board, numX, numO - 1, false);
// Restore board
board[i][j] = 'O';
}
}
}return ret;
}
推荐阅读
- 解决SyntaxError:|解决SyntaxError: invalid syntax
- vuex|vuex 基础结构
- cannot|cannot be read or is not a valid ZIP file
- mac升级之（xcrun:|mac升级之：xcrun: error: invalid active developer path, missing xcrun）
- element-ui表单验证例子（validateField验证部分表单）
- Kubernetes|Kubernetes stateful set讲解以及一个基于postgreSQL的具体例子
- 寻找写代码感觉（十六）之|寻找写代码感觉（十六）之 集成Validation做参数校验
- Unable|Unable to add window -- token null is not valid; is your activity running?
- RpcException:|RpcException: Invalid token! Failed to invoke method
- 解决vue项目中的“Invalid|解决vue项目中的“Invalid Host header”