problem description
Alice and Bob are playing tic-tac-toe.
the rules of tic-tac-toe chess game are simple: two people take turns to put pieces on the 3x3 board, Alice puts "X", Bob plays "O", and Alice takes the lead. When the same piece occupies three squares of a row, a column, or a diagonal, the game ends and the holder of the piece wins. When the chessboard is filled, the game is over and the two sides are tied.
Alice devised a method for scoring chess games:
-for situations where Alice has won, the score is (the number of blanks on the chessboard + 1);
-for situations where Bob has won, the score is-(the number of blank squares on the chessboard + 1);
-for a draw, the score is 0;
for example, in the picture above, Alice has won and there are two spaces on the chessboard, so the situation is divided into 2-1-3.
because Alice doesn"t like computing, he asks you, who is good at programming, if both play chess with the best strategy, what will be the final score in the current situation?
input format
the first line of input contains a positive integer T that represents the number of groups of data.
each set of data input has three rows, with three integers in each row, separated by spaces to represent the state of each grid on the chessboard. 0 means the grid is empty, 1 means "X" in the lattice, and 2 means "O" in the lattice. Make sure there are no other states.
make sure that the input situation is legal. (that is, to ensure that the input situation can be reached through the line chess, and that there is no situation in which both parties win at the same time.)
ensure that the input situation is the turn of the Alice line chess.
output format
for each set of data, output an integer in a row, indicating the score of the current situation.
sample input
3
1 21
212
0 00
21
0 21
0 02
00
0 000
0 000
sample output
3
-4
0
sample description
first group of data:
Alice puts the chess pieces in the lower left corner (or lower right corner), and the problem description can be reached.
3 is the maximum score in a situation that can be achieved by an Alice queen.
second set of data:
Bob has won (pictured), with a score of-(3-1) =-4.
third set of data:
in tic-tac-toe chess, if both sides adopt the optimal strategy, the game is tied, and the final score is 0.
data size and convention
for all evaluation use cases, 1 T 5.
look at what the bosses on the Internet use against search. It only takes about 50 lines. I haven"t learned it yet, and I don"t quite understand
. My own idea is very simple, that is, the strategy of simulating people to play chess, but I can"t get a full score. Only 70
strategies are as follows: if you can make three, play there;
4
I don"t know if it"s the wrong way of thinking or what"s wrong. I can"t get a full score
I"d like to ask if there"s anything wrong with this strategy