MYQ8 - The National Game
Prasanna and Nithin had mastered Thuvax's national game, TicTacToe.
TicTacToe is a board game for two players, x and o, who take turns (alternatively) marking the spaces in a 3×3 grid with their signs 'x' and 'o' respectively. The x player goes first. The player who succeeds in placing three of his signs in a horizontal, vertical, or diagonal row wins the game and the game stops there.
While returning from a TicTacToe tournament, Prasanna and Nithin find a tictactoe like grid. They decide to continue playing from the state the board was in. Help Nithin find whether the next person to move will win/lose or whether the game will result in a tie (assuming both players play optimally), or if such a state is invalid.
First line of the input contains a number T (1<=T<=10^6), followed by 4*T lines. The first line of each testcase is empty and the next 3 lines show the state of the game.
Print win/lose/tie/invalid for each testcase on a separate line.
... Output: lose
Case 1: Player x can win by placing x in either last cell of the middle row, or the first cell of the last row. So the next player, o, cant prevent him from winning from this state.
Case 2: It is completed game, as you can see no one has won. So, it has ended in a tie.
Case 3: Player x should have started the game. Hence such a state can never be reached.
I really cant figure out on which test cases why program fails. I would find it extremely helpful if you could provide some test cases or the number of test cases for which my program fails.
Time limits are 1s-30s. There is at least one test for each 1s and 30s time limits, but there also may by some case with 5s limit.
The Time limit is 30s, but the judge gives TLE within 5 secs. Is something wrong?
Correct sample output is: