2013
11-12

# Tic-Tac-Toe

In the game of tic-tac-toe, two players take turns marking squares of an initially empty 3 × 3 grid with either X’s or O’s. The first player always marks squares using X’s, whereas the second player always marks squares using O’s. If at any point during the game either player manages to mark three consecutive squares in a row, column, or diagonal with his/her symbol, the game terminates.

Given a board configuration, your goal is to determine whether the board configuration represents the possible final state of a valid tic-tac-toe game.

The input test file will contain multiple cases. Each test case consists of a single line containing 9 characters, which represent the 9 squares of a tic-tac-toe grid, given one row at a time. Each character on the line will either be ‘X’, ‘O’ (the letter O), or ‘.’ (indicating an unfilled square). The end-of-file is marked by a single line containing the word “end”.

For each input test case, write a single line containing either the word “valid” or “invalid” indicating whether the given board configuration is the final state of some possible tic-tac-toe game.

XXXOO.XXX
XOXOXOXOX
OXOXOXOXO
XXOOOXXOX
XO.OX...X
.XXX.XOOO
X.OO..X..
OOXXXOOXO
end

invalid
valid
invalid
valid
valid
invalid
invalid
invalid

//* @author
import java.util.Scanner;

public class Main {
Scanner cin = new Scanner(System.in);
int n;

public void inPut() {
n = cin.nextInt();

reverse();
}

private void reverse() {
if (n == 1) {
System.out.println(0);
} else {
if (n == 2) {
System.out.println(1);
System.out.println(2 + " " + 1 + " " + 0);
} else {
if (n % 2 == 0) {
int m = (n + 1) / 2 + 1;
System.out.println(m);
print(n, m);
} else {
if(n % 2 != 0) {
int m = (n + 1) / 2;
System.out.println(m);
print(n, m);
}
}
}
}
}

void print(int n, int m) {
if (n % 2 != 0) {
for (int i = 0; i < m - 1; i++) {
System.out.println((n / 2 + i + 1) + " " + 2 + " " + i);
}
System.out.println(1 + " " + (n - 1) / 2 + " " + (n - 1) / 2);

} else {
for (int i = 0; i < m - 2; i++) {
System.out.println((n / 2 + i + 1) + " " + 2 + " " + (i + 1));
}
System.out.println(2 + " " + (n - 1) / 2 + " " + (n) / 2);
System.out.println(1 + " " + 1 + " " + (n - 1));

}
}

public static void main(String[] args) {
new Main().inPut();
}

}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。