TOE1  TicTacToe ( I )
Tic Tac Toe is a child's game played on a 3 by 3 grid. One player, X, starts by placing an X at an unoccupied grid position. Then the other player, O, places an O at an unoccupied grid position. Play alternates between X and O until the grid is filled or one player's symbols occupy an entire line (vertical, horizontal, or diagonal) in the grid.
We will denote the initial empty Tic Tac Toe grid with nine dots. Whenever X or O plays we fill in an X or an O in the appropriate position. The example below illustrates each grid configuration from the beginning to the end of a game in which X wins.
Your job is to read a grid and to determine whether or not it could possibly be part of a valid Tic Tac Toe game. That is, is there a series of plays that can yield this grid somewhere between the start and end of the game?
Input
The first line of input contains N, the number of test cases. 4N1 lines follow, specifying N grid configurations separated by empty lines.
Output
For each case print "yes" or "no" on a line by itself, indicating whether or not the configuration could be part of a Tic Tac Toe game.
Example
Input: 2 X.O OO. XXX O.X XX. OOO Output: yes no
hide comments
tsunami_98:
20190701 17:30:30
Great Problem ...thanks 

ahmed ashry:
20190223 00:51:21
 Simple BFS will cover it.


cod_r:
20181109 15:23:05
Do a quick bfs over it! 

vvector:
20180928 14:16:43
Solution is very simple. i used only number of X and O and also number of winning lines. 

sinersnvrsleep:
20180402 14:20:24
nice question we are over complicating it it has a simple solution 

shahin mahmud:
20180115 12:49:31
you should know


cake_is_a_lie:
20170307 11:47:13
To the people complaining there are a lot of corner cases, I will say this: there is an elegant solution that is very simple to implement; if you have a lot of corner cases, you're overcomplicating it. 

Akash Garg:
20160528 08:55:06
Instead of checking whether a configuration is valid, just play the game once and store all possible configurations in a map. O(1) time for checking if something is valid or not. And just few thousand possible configurations possible. 

enigmus:
20160225 13:15:29
I would advise people not to pursue this problem. It's easy to think of the solution but annoying to implement. There are so many possible exception one has to be aware about to get AC 

minhthai:
20160115 09:45:57
just be careful :) 
Added by:  Camilo Andrés Varela León 
Date:  20061214 
Time limit:  0.161s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Waterloo local 2002.09.21 