TCTCTOE - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester & Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Depth First Search

PROBLEM

Tic-tac-toe is a game played between two players on a 3 \times 3 grid. In a turn, a player chooses an empty cell and places their symbol on the cell. The players take alternating turns, where the player with the first turn uses the symbol X and the other player uses the symbol O. The game continues until there is a row, column, or diagonal containing three of the same symbol (X or O), and the player with that token is declared the winner. Otherwise if every cell of the grid contains a symbol and nobody won, then the game ends and it is considered a draw.

You are given a tic-tac-toe board A after a certain number of moves, consisting of symbols O, X, and underscore(\_). Underscore signifies an empty cell.

Print

  • 1: if the position is reachable, and the game has drawn or one of the players won.
  • 2: if the position is reachable, and the game will continue for at least one more move.
  • 3: if the position is not reachable.

QUICK EXPLANATION

  • Each state of the game can be represented as a node in a graph, edge u to v denoting that from state u, it is possible to reach state v in one move and the game did not end at state u.
  • For a given state, if it is reachable from start state, and there’s no outgoing edge from that state, the answer is 1.
  • For a given state, if it is reachable from start state, and there’s there’s atleast one outgoing edge from that state, the answer is 2.

EXPLANATION

There are two solutions for this problem. One solution is generic approach to such problems, by modelling the game states as a graph, second approach is specific to this problem, figuring out cases in order to determine if it is reachable, and if yes, whether the game has ended or not.

We’d discuss the graph approach, though case based approach can be found in Setter’s solution section.

Let’s represent each state of the grid as a node in graph.
What is the number of nodes in this graph? Each cell can have either of the three characters at any time, and there are 9 such positions, hence there are 3^9 = 19683 states. Hence, we can easily store the answers for all states, and answer queries in O(1).

Let’s add edge from node u to node v, if and only if the game hasn’t ended at state u and there exists a move which converts board in state u to board in state v. From each state, there can be at most 9 outgoing edges.

We start from node corresponding to empty grid, calling this the source state.

Referring to problem statement, answer is 1 is the position is reachable, and either one of the player has won, or there’s no move possible. In terms of our graph, it is equivalent to the target state node being reachable from source state node, and there’s no outgoing edge from target state node.

Similarly, answer is 2 if target state node is reachable from source state node and there’s at least 1 outgoing edge from target state node.

Hence, all we need to do is to

  • Find a way to encode grid state into a node id.
  • Given a board, check if either player won, or the grid is completely filled.

Grid encoding can be done by numbering cells of grid from 0 to 8 and replacing characters by 0, 1 and 2, and computing \displaystyle\sum_{i = 0}^8 g(i) * 3^i, g(i) denoting the value at ith cell.

You may refer DFS implementation in tester solution.

TIME COMPLEXITY

The time complexity for DFS approach is O(3^9*9+T).
The time complexity for case based implementation is O(3^2) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;
  
const int maxt = (int)pow(3, 9);

int main()
{   
    int t; cin >> t;
    while(t--){
        string s[3];
        int cX = 0, cO = 0, winX = 0, winO = 0;
        // row
        for(int i = 0; i < 3; i++){
            cin >> s[i];
            int cXr = 0, cOr = 0;
            for(int j = 0; j < 3; j++){
                if(s[i][j] == 'X')cXr++;
                else if(s[i][j] == 'O')cOr++;
            }
            cX += cXr; cO += cOr; 
            if(cXr == 3)winX++;
            else if(cOr == 3)winO++;
        }
        // column
        for(int j = 0; j < 3; j++){
            int cXc = 0, cOc = 0;
            for(int i = 0; i < 3; i++){
                if(s[i][j] == 'X')cXc++;
                else if(s[i][j] == 'O')cOc++;
            }
            if(cXc == 3)winX++;
            else if(cOc == 3)winO++;
        }
        // left diagonal
        int cXd = 0, cOd = 0;
        for(int i = 0; i < 3; i++){
            if(s[i][i] == 'X')cXd++;
            else if(s[i][i] == 'O')cOd++;
        }
        if(cXd == 3)winX++;
        else if(cOd == 3)winO++;
        // right diagonal
        cXd = 0; cOd = 0;
        for(int i = 0; i < 3; i++){
            if(s[i][2 - i] == 'X')cXd++;
            else if(s[i][2 - i] == 'O')cOd++;
        }
        if(cXd == 3)winX++;
        else if(cOd == 3)winO++;
        int ans = 2;
        if((winX >= 1 && winO >= 1) || !(cX == cO || cX == cO + 1) || (winO >= 1 && cX == cO + 1) || (winX >= 1 && cX == cO))ans = 3;
        else if((winX >= 1 || winO >= 1) || (cX + cO == 9))ans = 1;
        cout << ans << endl;
    }
} 
Tester's Solution
import java.util.*;
import java.io.*;
class TCTCTOE{
    //SOLUTION BEGIN
    int[] pow3, state;
    void pre() throws Exception{
        pow3 = new int[10];
        pow3[0] = 1;
        for(int i = 1; i< pow3.length; i++)pow3[i] = pow3[i-1]*3;
        
        state = new int[pow3[9]];
        Arrays.fill(state, 3);
        //1 -> reachable and ended
        //2 -> reachable and going on
        //3 -> not reachable
        char[][] start = new char[][]{
            {'_', '_', '_'},
            {'_', '_', '_'},
            {'_', '_', '_'}
        };
        dfs(start, 'X');
    }
    void dfs(char[][] g, char turn){
        int id = encode(g);
        if(state[id] != 3)return;//This state is already processed
        if(ended(g)){
            state[id] = 1;
            return;
        }
        state[id] = 2;
        for(int i = 0; i< g.length; i++){
            for(int j = 0; j< g[i].length; j++){
                if(g[i][j] == '_'){
                    g[i][j] = turn;
                    dfs(g, (char)('X' + 'O'-turn));
                    g[i][j] = '_';
                }
            }
        }
    }
    void solve(int TC) throws Exception{
        char[][] grid = new char[3][];
        for(int i = 0; i< grid.length; i++)grid[i] = n().toCharArray();
        pn(state[encode(grid)]);
    }
    //Checks if the game is finished or not.
    boolean ended(char[][] g){
        boolean win = false;
        for(int i = 0; i< 3; i++){
            win |= g[i][0] != '_' && g[i][0] == g[i][1] && g[i][1] == g[i][2];
            win |= g[0][i] != '_' && g[0][i] == g[1][i] && g[1][i] == g[2][i];
        }
        win |= g[0][0] != '_' && g[0][0] == g[1][1] && g[1][1] == g[2][2];
        win |= g[0][2] != '_' && g[0][2] == g[1][1] && g[1][1] == g[2][0];
        
        boolean filled = true;
        for(char[] row:g)
            for(char cell:row)
                filled &= cell != '_';
        return win || filled;
    }
    int encode(char[][] g){
        int id = 0;
        for(int i = 0; i< g.length; i++)
            for(int j = 0; j< g[i].length; j++)
                id += pow3[i*3+j]*get(g[i][j]);
        return id;
    }
    int get(char ch){
        switch(ch){
            case '_':return 0;
            case 'X':return 1;
            case 'O':return 2;
            default: return -1;
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new TCTCTOE().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

6 Likes

can anyone tell me why the hell my code is getting WA.

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef {
	public static void main(String[] args) throws java.lang.Exception {
        BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(inp.readLine());
        while (t-- > 0) {
            String a = inp.readLine();
            String b = inp.readLine();
            String c = inp.readLine();
            int countX = 0, count_ = 0, countO = 0;
            for (int i = 0; i < 3; i++) {
                // a String
                if (a.charAt(i) == 'X') {
                    countX++;
                } else if (a.charAt(i) == 'O') {
                    countO++;
                } else {
                    count_++;
                }

                // b String
                if (b.charAt(i) == 'X') {
                    countX++;
                } else if (b.charAt(i) == 'O') {
                    countO++;
                } else {
                    count_++;
                }

                // c String
                if (c.charAt(i) == 'X') {
                    countX++;
                } else if (c.charAt(i) == 'O') {
                    countO++;
                } else {
                    count_++;
                }
            }
//            System.out.println(countX + " " + countO + " " + count_);
            int countXWinner = checkWinnerX(a, b, c, 'X');
            int countOWinner = checkWinnerO(a, b, c, 'O');
//            System.out.println(countXWinner + " " + countOWinner);
            int ans = 3;
            if (countX == countO) {
                if (countXWinner == 0) {
                    if (countOWinner > 0) {
                        // System.out.println(1);
                        ans = 1;
                    } else {
                        // System.out.println(2);
                        ans = 2;
                    }
                } else {
                    // System.out.println(3);
                    ans = 3;
                }
            } else if (countX == (countO + 1)) {
                if (count_ > 0) {
                    if (countXWinner > 0 && countOWinner > 0) {
                        // System.out.println(3);
                        ans = 3;
                    } else if (countXWinner > 0 && countOWinner == 0) {
                        // System.out.println(1);
                        ans = 1;
                    } else {
                        // System.out.println(2);
                        ans = 2;
                    }
                } else {
                    if ((countXWinner > 0 && countOWinner > 0) || (countOWinner > 0)) {
                        // System.out.println(3);
                        ans = 3;
                    } else  {
                        // System.out.println(1);
                        ans = 1;
                    }
                }
            } else {
                // System.out.println(3);
                ans = 3;
            }
            System.out.println(ans);
        }
    }

    private static int checkWinnerO(String a, String b, String c, char o) {
        int countWin = 0;
        if (a.equals("OOO")) {
            countWin++;
        }
        if (b.equals("OOO")) {
            countWin++;
        }
        if (c.equals("OOO")) {
            countWin++;
        }
        if (a.charAt(0) == o && b.charAt(0) == o && c.charAt(0) == o) {
            countWin++;
        }
        if (a.charAt(1) == o && b.charAt(1) == o && c.charAt(1) == o) {
            countWin++;
        }
        if (a.charAt(2) == o && b.charAt(2) == o && c.charAt(2) == o) {
            countWin++;
        }
        if (a.charAt(0) == o && b.charAt(1) == o && c.charAt(2) == o) {
            countWin++;
        }
        if (a.charAt(2) == o && b.charAt(1) == o && c.charAt(0) == o) {
            countWin++;
        }
        return countWin;
    }

    private static int checkWinnerX(String a, String b, String c, char x) {
        int countWin = 0;
        if (a.equals("XXX")) {
            countWin++;
        }
        if (b.equals("XXX")) {
            countWin++;
        }
        if (c.equals("XXX")) {
            countWin++;
        }
        if (a.charAt(0) == x && b.charAt(0) == x && c.charAt(0) == x) {
            countWin++;
        }
        if (a.charAt(1) == x && b.charAt(1) == x && c.charAt(1) == x) {
            countWin++;
        }
        if (a.charAt(2) == x && b.charAt(2) == x && c.charAt(2) == x) {
            countWin++;
        }
        if (a.charAt(0) == x && b.charAt(1) == x && c.charAt(2) == x) {
            countWin++;
        }
        if (a.charAt(2) == x && b.charAt(1) == x && c.charAt(0) == x) {
            countWin++;
        }
        return countWin;
    }
}

I Have already tested manually approx 25 extra test case.

I think you missed edge cases such as
XXX this is a valid path
0X0
0X0 as
X_X is valid
0X0
0X0
there are 4*3+4+6 = 22 such edge cases

1 Like

Simple JAVA Approach

  import java.util.*;
    import java.lang.*;
    import java.io.*;
    class Main{
         static int a=0;
         static int b=0;
         static int c=0;
        public static void numbers(String[] ttt){
              int countX=0;
              int countO=0;
              int count_=0;
              for(int i=0;i<3;i++){
                  String str=ttt[i];
                  for(int j=0;j<3;j++){
                      char ch=str.charAt(j);
                      if(ch=='X'){
                          countX++;
                      }else if(ch=='O'){
                          countO++;
                      }else{
                          count_++;
                      }
                  }
              }
              a=countX;
              b=countO;
              c=count_;
        }
        public static int howManyWon(String[] ttt){
              int xRow=0;  
              int xCol=0;
              int Owon=0;
              int dxwon=0;
              int dowon=0;
              // check horizontally
              String p=ttt[0];
              String q=ttt[1];
              String r=ttt[2];
              if(p.equals("XXX")){
                  xRow++;
              }else if(p.equals("OOO")){
                  Owon++;
              }
              
              if(q.equals("XXX")){
                  xRow++;
              }else if(q.equals("OOO")){
                  Owon++;
              }
              
              if(r.equals("XXX")){
                  xRow++;
              }else if(r.equals("OOO")){
                  Owon++;
              }
              // check Vertically
              String x=""+p.charAt(0)+q.charAt(0)+r.charAt(0);
              String y=""+p.charAt(1)+q.charAt(1)+r.charAt(1);
              String z=""+p.charAt(2)+q.charAt(2)+r.charAt(2);
               if(x.equals("XXX")){
                  xCol++;
              }else if(x.equals("OOO")){
                  Owon++;
              }
              
              if(y.equals("XXX")){
                  xCol++;
              }else if(y.equals("OOO")){
                  Owon++;
              }
              
              if(z.equals("XXX")){
                  xCol++;
              }else if(z.equals("OOO")){
                  Owon++;
              }
              
              // diagnolly 
              
              String d1=""+p.charAt(0)+q.charAt(1)+r.charAt(2);
              String d2=""+r.charAt(0)+q.charAt(1)+p.charAt(2);
               if(d1.equals("XXX")){
                  dxwon++;
              }else if(d1.equals("OOO")){
                  dowon++;
              }
              
              if(d2.equals("XXX")){
                  dxwon++;
              }else if(d2.equals("OOO")){
                  dowon++;
              }
              
              int Xwon=xRow+xCol;
              
              if((Xwon==1 && Owon==0) || (xRow==1 && xCol==1 ) || dxwon==2 || dxwon==1){
                  // x actually
                 
                  return 1;
              }else if((Xwon==0 && Owon==1) || dowon==2 || dowon==1){
                  // O actually won
                  return 0;
              }else if(Xwon==0 && Owon==0 && dxwon==0 && dowon==0){
                  return 2;
              }else{
                  return 3;
              }
              
        }
    	public static void main (String[] args) throws java.lang.Exception
    	{
    	   Reader sc=new Reader();
    	   int T=sc.nextInt();
    	   for(int t=0;t<T;t++){
    	  // sc.nextLine();
    	   String ttt[]=new String[3];
    	   for(int i=0;i<3;i++){
    	       ttt[i]=sc.readLine();
    	   }
    	   numbers(ttt); // x, o , _ numbers
    	   int l=howManyWon(ttt); // who wons
         
         if(a-b>1){
           System.out.println("3");
           continue;
         }
          if(b>a){
           System.out.println("3");
           continue;
         }
         if(l==3){
                System.out.println("3");
                continue;
         }
         if(l==1){
           if(a!=b+1){
             System.out.println("3");
           }else{
             System.out.println("1");
           }
           continue;
         }
         if(l==0){
            if(a!=b){
              System.out.println("3");
            }
            else{
              System.out.println("1");
            }
            continue;
         }
         if(l==2){
            if(c==0){
              System.out.println("1");
            }
            else{
              System.out.println("2");

            }
            continue;
         }
    	   }
    	}
    }

This was my code in JAVA. It got accepted

These are the Test Cases :

25
XXX
OXO
XOO
XOX
___
___
X_O
_OX
O_X
OOO
OOO
OOO
XXX
OOO
OOO
___
___
___
XOX
XXO
O_O
XXX
OOO
___
_OX
OX_
XO_
OXX
XOO
OXX
OXO
XOX
XXO
XOX
OXO
OXO
XOX
OX_
XO_
XO_
___
__X
XOX
__X
_O_
XOX
XXO
O_O
XXX
OOO
___
OOO
XXX
XXX
XOO
OOO
OXX
XXX
OOX
OOX
XOO
OXO
XXX
XOO
_X_
XXX
XOX
OXO
XOX
XXX
XXX
XXX
OOO
___
___

Having Respected Output as :

1
2
1
3
3
2
2
3
3
1
3
3
1
2
2
2
3
3
3
1
1
3
1
3

Check for this-
XOO
XOO
XXX
Expected output for that should be 1

Yes I am getting 1 for the test case -

XOO
XOO
XXX

:man_shrugging:

Your code is failing in this test case. Answer should be 3 your code will give 2.

1
OXX
XOX
__O

Thanks Man, I got my Mistake.

Hey I wonder why online compiler is giving wrong answer even though I have checked most of the edge cases

#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?++i:--i)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define test cout<<"This is TEST********\n";
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define sz(c) (int)c.size()
#define ans(x) cout<<x<<'\n';
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pl;
typedef vector<int>		vi;
typedef vector<ll>		vl;
typedef vector<pii>		vpii;
typedef vector<pl>		vpl;
typedef vector<vi>		vvi;
typedef vector<vl>		vvl;


void solve() {
	int i, j,k, row[3] = {0}, col[3] = {0}, diag[2] = {0},  win = -1, nx=0, ny=0;
	string n;
	fo(i, 3) {
		cin >> n;
		fo(j, 3)
		{	k=int(n[j]);
			row[i] += k; 
			col[j] += k; 
			if (i == j) diag[0] += k; 
			if (i == 2 - j) diag[1] += k;
			if(k==88)nx++;
			else if(k==79)ny++;
}
	}
	if ((nx - ny) > 1 || ny>nx ) {
		ans(3); return;
	}
	
	fo(i, 3) {

		if (row[i] == 264 || col[i]==264 || diag[i%2]==264) {

			if(win==-1) {if(nx<=ny){ans(3);return;}
			win=0;}
			else if(win!=0){ans(3);return;}
		}

		if (row[i] == 237 || col[i]==237 || diag[i%2]==237) {

			if(win==-1) { if(ny<nx){ans(3);return;}win=0;}
			else if(win!=1){ans(3);return;}
		}

		}
	if (nx+ny==9 || win!=-1) {
		ans(1);return;
	}
	
	ans(2);


}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int t;
	cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

CodeChef: Practical coding for everyone @darshancool25. I code the same logic (as per ur video editorial) but still there is an issue and I am unable to find that.

Because you checked “most” instead of “all” :stuck_out_tongue:

1
___
OOO
XXX
1 Like
1
__X
_XO
XOO
if(res>1) cout<<"3\n";

Is the mistake.

1
XXX
OXO
XOO

Should be 1, not 3

Damn in my checking function I copied the win checker for X to O but forgot to change the win variable value to 1.
Thanks man

1 Like

@dharshancool25
can you please explain me that why should we take the condition
!((x==o)||(x==o+1)) in that why should we use ! this .
if two person wins the game ,we need to check that the count of x and o should be equal or greater than one if any one of its is true can’t we print 3 .why should we go for ! this sir.
thank you in advance

tried 30 + cases .pls tell me that one damn case where its going wrong

#include
using namespace std;

int main()
{
long long int T;
cin>>T;
for( long long int k=0;k<T;k++)
{ int X=0,O=0;
char r1[3],r2[3],r3[3];
cin>>r1[0]>>r1[1]>>r1[2];
cin>>r2[0]>>r2[1]>>r2[2];
cin>>r3[0]>>r3[1]>>r3[2];

    for(int i=0;i<3;i++)//counting X and O
    {
        if(r1[i]=='X')
        X++;
        else if(r1[i]=='O')
        O++;

        if(r2[i]=='X')
        X++;
        else if(r2[i]=='O')
        O++;

        if(r3[i]=='X')
        X++;
        else if(r3[i]=='O')
        O++;

    }
    bool o2=false;
    bool d=false;
    bool h=false;
    bool v=false;
    bool won=false;
    bool win2=false;  /**more than one winner case is
                        not reachable except for 
                        the cases where x wins through
                        two ways simultaneously for eg.XXX
                                        OXO
                                        OOX
                        i make win2 true whenever this happens**/
                        
    
    int winner=0;
    //deciding if anyone won
    for(int i=0;i<3;i++)
    {
        if(r1[i]==r2[i] && r2[i]==r3[i] && (r3[i]=='X' || r3[i]=='O') )
        {   if(r3[i]=='O')
            {o2=true;} 
            won=true;
            winner++;
            if(r1[i]=='X')
            {v=true;}
        }
    }
    
    
    if(r1[0]==r1[1] && r1[1]==r1[2] && (r1[2]=='X' || r1[2]=='O') )
    {   if(r1[2]=='O')
        {o2=true;} 
        won=true;
        winner++;
        if(r1[0]=='X')
        {h=true;}
    }
         
    if(r2[0]==r2[1] && r2[1]==r2[2] && (r2[2]=='X' || r2[2]=='O') )
    {   if(r2[2]=='O')
        {o2=true;} 
        won=true;
        winner++;
        if(r2[0]=='X')
        {h=true;}
    }
    if(r3[0]==r3[1] && r3[1]==r3[2] && (r3[2]=='X' || r3[2]=='O') )
    {   if(r3[2]=='O')
        {o2=true;} 
        won=true;
        winner++;
        if(r3[0]=='X')
        {h=true;}
    }
    
    if( ( ( r1[0]==r2[1] && r2[1]==r3[2] ) || ( r1[2]==r2[1] && r2[1]==r3[0] ) ) && ( r2[1]=='X' || r2[1]=='O') )
    {   if(r2[1]=='O')
        {o2=true;} 
        won=true;
        winner++;
        if(r2[1]=='X')
        {
            d=true;
        }
        if(( r1[0]==r2[1] && r2[1]==r3[2] ) && ( r1[2]==r2[1] && r2[1]==r3[0] ) && r2[1]=='X')
        {win2=true;}
    }
    
    if(h==true && v==true || d==true && h==true || v==true && d==true)/**this checks if two wins
                                                                        have happened simultaneously**/ 
     
    { win2=true;}
    
    
    if(X-O==1 || X-O==0)//as we start with X ,O can never be more than X
    {
        if(X+O!=9 && won==false)
        {cout<<2<<endl;}
        else if ((winner>1 && win2==false ) || ( o2==true && X-O==1) )
        {cout<<3<<endl;}
        else
        {cout<<1<<endl;}
    }
    else
    {
        cout<<3<<endl;
    }
    
    
}
return 0;

}

1
___
___
__O

@ojas_17

https://www.codechef.com/viewsolution/46624166
Can someone please provide test case(s) where this wont work. Have been trying for a long time

#include <bits/stdc++.h>
#define int long long int
using namespace std;

bool hasWonX = false, hasWonO = false, rowWinX = false, rowWinO = false, colWinX = false, colWinO = false, diagWinX = false, diagWinO = false;

bool oneKindOfWinX()
{
    if ((rowWinX && !colWinX && !diagWinX) || (!rowWinX && colWinX && !diagWinX) || (!rowWinX && !colWinX && diagWinX))
        return true;
    else
        return false;
}

bool oneKindOfWinO()
{
    if ((rowWinO && !colWinO && !diagWinO) || (!rowWinO && colWinO && !diagWinO) || (!rowWinO && !colWinO && diagWinO))
    {
        // cout << (rowWinO && !colWinO && !diagWinO) << " " << (!rowWinO && colWinO && !diagWinO) << " " << (!rowWinO && !colWinO && diagWinO) << "\n";
        return true;
    }
    else
    {
        return false;
    }
}

int32_t main()
{
#ifndef ONLINE_JUDGE
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;
    while (t--)
    {
        hasWonX = false, hasWonO = false, rowWinX = false, rowWinO = false, colWinX = false, colWinO = false, diagWinX = false, diagWinO = false;
        string r1, r2, r3;
        cin >> r1 >> r2 >> r3;

        int spaceCount = 0, oCount = 0, xCount = 0;

        for (int i = 0; i < 3; i++)
        {
            if (r1[i] == '_')
                spaceCount++;
            if (r2[i] == '_')
                spaceCount++;
            if (r3[i] == '_')
                spaceCount++;
            if (r1[i] == 'X')
                xCount++;
            if (r2[i] == 'X')
                xCount++;
            if (r3[i] == 'X')
                xCount++;
            if (r1[i] == 'O')
                oCount++;
            if (r2[i] == 'O')
                oCount++;
            if (r3[i] == 'O')
                oCount++;
        }

        // Case 1 - game is reachable and decided
        // Case 2 - game is reachable and not decided
        // Case 3 - game is unreachable

        //Row wins
        if ((r1[0] == r1[1] && r1[1] == r1[2] && r1[1] == 'X') || (r2[0] == r2[1] && r2[1] == r2[2] && r2[1] == 'X') || (r3[0] == r3[1] && r3[1] == r3[2] && r3[1] == 'X'))
        {
            hasWonX = true;
            rowWinX = true;
        }
        if ((r1[0] == r1[1] && r1[1] == r1[2] && r1[1] == 'O') || (r2[0] == r2[1] && r2[1] == r2[2] && r2[1] == 'O') || (r3[0] == r3[1] && r3[1] == r3[2] && r3[1] == 'O'))
        {
            hasWonO = true;
            rowWinO = true;
        }

        //Col wins
        if ((r1[0] == r2[0] && r2[0] == r3[0] && r2[0] == 'X') || (r1[1] == r2[1] && r2[1] == r3[1] && r2[1] == 'X') || ((r1[2] == r2[2] && r2[2] == r3[2] && r2[2] == 'X')))
        {
            hasWonX = true;
            colWinX = true;
        }
        if ((r1[0] == r2[0] && r2[0] == r3[0] && r2[0] == 'O') || (r1[1] == r2[1] && r2[1] == r3[1] && r2[1] == 'O') || ((r1[2] == r2[2] && r2[2] == r3[2] && r2[2] == 'O')))
        {
            hasWonO = true;
            colWinO = true;
        }

        //Diag wins
        if ((r1[0] == r2[1] && r2[1] == r3[2] && r2[1] == 'X') || (r3[0] == r2[1] && r2[1] == r1[2] && r2[1] == 'X'))
        {
            hasWonX = true;
            diagWinX = true;
        }
        if ((r1[0] == r2[1] && r2[1] == r3[2] && r2[1] == 'O') || (r3[0] == r2[1] && r2[1] == r1[2] && r2[1] == 'O'))
        {
            hasWonO = true;
            diagWinO = true;
        }

        //Case break - if x greater or o greater
        if(xCount - oCount > 1 || oCount - xCount > 1 || (oCount > xCount && hasWonX) || (xCount > oCount && hasWonO) )
        {
            cout << "3\n";
            continue;
        }

        //Case 1a) - X wins
        if (hasWonX && oneKindOfWinX() && !hasWonO)
        {
            cout << "1\n";
            continue;
        }
        // Case 1b) - O wins
        else if (hasWonO && oneKindOfWinO() && !hasWonX)
        {
            cout << "1\n";
            continue;
        }
        // Case 1c) - Draw
        else if (spaceCount == 0 && !hasWonO && !hasWonO)
        {
            cout << "1\n";
            continue;
        }

        //Case 2) - Continue
        else if (!hasWonO && !hasWonX && spaceCount > 0)
        {
            cout << "2\n";
            continue;
        }

        // Case 3) - Unreachable
        else if ((hasWonO && hasWonX) || !oneKindOfWinO() || oneKindOfWinX())
        {
            cout << "3\n";
            continue;
        }
        else
            cout << "why? \n";
        // If it reaches here I am stupid

        // cout << "hasWonX " << hasWonX << " "
        //      << "hasWonO " << hasWonO << " "
        //      << "rowWinX " << rowWinX << " "
        //      << "rowWinO " << rowWinO << " "
        //      << "colWinX " << colWinX << " "
        //      << "colWinO " << colWinO << " "
        //      << "diagWinX " << diagWinX << " "
        //      << "diagWinO " << diagWinO << "\n";
    }
    return 0;
}```