Algorithm


Problem link- https://www.spoj.com/problems/TOE1/

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

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>

using namespace std;

string g[3];

bool checkrows(char winner){
	for(int i=0;i<3;i++){
		if(g[i][0]==winner&&g[i][1]==winner&&g[i][2]==winner){
			return true;
		}
	}
	return false;
}
bool checkcols(char winner){
	for(int i=0;i<3;i++){
		if(g[0][i]==winner&&g[1][i]==winner&&g[2][i]==winner){
			return true;
		}
	}
	return false;
}
bool checkdiagnols(char winner){
		if(g[0][0]==winner&&g[1][1]==winner&&g[2][2]==winner){
			return true;
		}
		if(g[0][2]==winner&&g[1][1]==winner&&g[2][0]==winner){
			return true;
		}
		return false;
}

int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		bool possible=true;
		for(int i=0;i<3;i++){
			cin>>g[i];
		}
		int xcount=0,ocount=0;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(g[i][j]=='X'){
					xcount++;
					continue;
				}
				if(g[i][j]=='O'){
					ocount++;
				}
			}
		}
		if(ocount>xcount){
			possible=false;
		}
		if((xcount-ocount)>1){
			possible=false;
		}
		//cout<<xcount<<" "<<ocount<<endl;
		bool winnerx=(checkrows('X')||checkcols('X')||checkdiagnols('X'));
		if(winnerx){
			if((xcount-ocount)!=1){
				possible=false;
			}
		}
		bool winnero=(checkrows('O')||checkcols('O')||checkdiagnols('O'));
		if(winnero){
			if((xcount-ocount)!=0){
				possible=false;
			}
		}
		if(winnerx==true&&winnero==true){
			possible=false;
		}
		if(possible){
			printf("yes\n");
		}
		else{
			printf("no\n");
		}
		if(n!=0){
			printf("\n");
		}
	}
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2
X.O
OO.
XXX
O.X
XX.
OOO

Output

x
+
cmd
yes
no

#2 Code Example with Java Programming

Code - Java Programming

#include<stdio.h>
char str[10],str1[4],str2[4],str3[4];

int main()
{
    int i,j,no_X,no_O,flag,win_X,win_O,t;

    scanf("%i",&t);

    while(t--)
    {
        no_X = no_O = flag = win_X = win_O = 0;

        scanf("%s%s%s",str1,str2,str3);

        str[0] = str1[0];
        str[1] = str1[1];
        str[2] = str1[2];
        str[3] = str2[0];
        str[4] = str2[1];
        str[5] = str2[2];
        str[6] = str3[0];
        str[7] = str3[1];
        str[8] = str3[2];

        for(i=0;    i<9;    i++)
        {
            if(str[i] == 'X')
                no_X++;
            else if(str[i] == 'O')
                no_O++;
        }

        if(str[4] != '.')
        {
            if(str[4] == 'O')
            {
                if((str[0] == 'O' && str[8] == 'O') || (str[1] == 'O' && str[7] == 'O') || (str[2] == 'O' && str[6] == 'O') || (str[3] == 'O' && str[5] == 'O'))
                    win_O = 1;
            }
            else
            {
                if((str[0] == 'X' && str[8] == 'X') || (str[1] == 'X' && str[7] == 'X') || (str[2] == 'X' && str[6] == 'X') || (str[3] == 'X' && str[5] == 'X'))
                    win_X = 1;
            }
        }

        if(str[1] != '.')
        {
            if(str[0] == 'O')
            {
                if((str[3] == 'O' && str[6] == 'O') || (str[1] == 'O' && str[2] == 'O'))
                    win_O =1;
            }

            else
            {
                if((str[3] == 'X' && str[6] == 'X') || (str[1] == 'X' && str[2] == 'X'))
                    win_X =1;
            }
        }

        if(str[8] != '.')
        {
            if(str[8] == 'O')
            {
                if((str[5] == 'O' && str[2] == 'O') || (str[7] == 'O' && str[6] == 'O'))
                    win_O = 1;
            }
            else
            {
                if((str[5] == 'X' && str[2] == 'X') || (str[7] == 'X' && str[6] == 'X'))
                    win_X = 1;
            }
        }

        if(win_X == 1 && win_O == 1)
            flag = 1;

        else
        {
            if(win_X == 1 && win_O == 0 && no_X != no_O + 1)
                flag = 1;

            else if(win_X == 0 && win_O == 1 && no_X != no_O)
                flag = 1;

            else if(no_X != no_O+1 && no_X != no_O)
            {
                flag = 1;
            }
        }


        if(flag)
            printf("no\n");
        else
            printf("yes\n");

    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2
X.O
OO.
XXX
O.X
XX.
OOO

Output

x
+
cmd
yes
no
Advertisements

Demonstration


SPOJ Solution-TOE1 Tic-Tac-Toe ( I )-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python