TOE1 - Tic-Tac-Toe ( 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.

subir imagenes

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. 4N-1 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
Rocker3011: 2014-04-12 23:24:27

it has been almost 2 years since i started on programming, this was my first classical problem, i failed misserably on solving it, now i come back and it was way more simple to solve. Even thought the problem is quite easy, it has trickie cases that are not obvious if you don't play the game

Last edit: 2014-04-12 23:24:54
Python: 2014-01-09 15:00:03

Consider winning cases of X and O with the plot that is allowed in each case. And you are done.

Sudhir Krishnakumar: 2013-12-31 18:05:45

AC! My 50th :D

SanchitK: 2013-12-16 18:10:27

@admin-please check my code. the judge gives WA even if it works for all the test cases mentioned.
problem id-10675772

aman jain: 2013-05-14 12:27:16

friends be careful:
in this x can win twice over diagonals.
not considering will lead to WA.

Last edit: 2013-05-14 13:30:41
killerz: 2013-03-27 11:34:41

@Tigran Galstyan
In case 1
XXO
OOX
OXX
chance num of X is 1 3 5 7 9
here O had won thus no extra X ,ie, game finishes at chance num 8 ; thus invalid !!!

Tigran Galstyan: 2013-03-03 18:35:48

@kamalesh why 1st case is "NO"??

Eslam Zanaty: 2013-02-20 15:36:17

@Viktor Fonic
this case prints YES its a valid case

Viktor Fonic: 2013-02-07 09:44:34

This one caused me a lot of trouble:
XOX
OXX
OOX
no

Apurva Kumar: 2013-01-20 10:51:20

Is X always playing first?If not then please explain 2nd test case.

Last edit: 2013-01-20 11:16:01

Added by:Camilo Andrés Varela León
Date:2006-12-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Waterloo local 2002.09.21