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
Simes: 2023-07-19 11:58:48

@sayedreda.
XXX
OOO
...

sayedreda: 2023-07-18 21:51:53

My Idea is as simple as counting number of x and number of o and x has to be greater than o at most 1 (1 || 0) and it gives WA i don't know why?
Some help!

ms2052001: 2022-07-10 20:09:23

I was insisting on getting this accepted without BFS and after 6 "Wrong answer" submissions, I managed to get it "Accepted" when I noticed that if (O) wins the game the number of points with (X) must equal the number of (O) points.

sachin_08: 2022-01-09 20:51:57

Try possible layouts using BFS.

mimi0007: 2021-05-19 19:54:45

I was stuck in these cases:
OOX
OOX
XXX
-yes

OXO
XXX
OXO
-yes

abhishek_r05: 2021-04-29 14:13:24

This can be solved without bfs , pretty easily. Just divide into some cases.

fatahchan: 2020-12-18 01:41:31

i honestly dont understand whats wrong with my code, I already test many test cases and it still says my answer is wrong, can someone take a look at my code
and tell me whats wrong

saad1439: 2020-07-06 18:57:49

Read the last statement carefully!
The grid is not supposed to be winning combination only rather it might be the anywhere of the game (from Starting to Ending )

reminder : Just simple tic-tac-toe game and so, there is no corner case to be handled.If you are thinking about corner cases you are complicating it.

Last edit: 2020-07-06 19:01:32
tosnejan: 2020-02-20 18:12:30

This one caused me a lot of trouble.
1
XXX
OXO
XOX
no

Last edit: 2020-02-20 18:12:40
tsunami_98: 2019-07-01 17:30:30

Great Problem ...thanks


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