11623 - Tic Tac Toe

[RC's]

Hi, is there anyone who has critical test case ? I think this problem is not very difficult but I kept getting WA. I used an 2D array to store the number of X or O's diagonally, vertically and horizontally.

[jurajz]

At the first sight, I think, that this problem is easy. But at the second sight, I don't think so For example, if m=3 and we find 3 consecutive 'X' in row, column or diagonal, this not automatically means, that X wins. Here is sample input and output from my AC program, some cases may be critical:

Input:

Code: Select all

22
1 1
X
1 1
O
1 1
.
2 1
X.
..
2 1
O.
..
2 1
..
..
3 3
OOO
.X.
X.X
3 3
OOO
XXX
...
3 3
OOO
.X.
XXX
3 3
XXO
OXX
XOO
3 3
..O
XX.
..X
3 3
OO.
XX.
O..
3 3
.XO
..X
...
5 3
O.O.O
.....
XXX.X
....X
OO..X
5 3
O.O.O
.....
XXX..
..X..
O.X..
5 3
O.O.O
.....
..X..
.XXX.
O.X..
5 3
O.O.O
...X.
XXXX.
...X.
OO...
7 5
O.O.O.O
O.O.O.O
X.X.X..
.XXX...
..X....
OXXXO..
XOXOX..
7 4
O.O.O.O
O.O.O.O
X.X.X..
.XXX...
..X....
OXXXO..
XOXOX..
7 3
O.O.O.O
O.O.O.O
X.X.X..
.XXX...
..X....
OXXXO..
XOXOX..
6 3
X....O
.X...O
..X...
...X..
O...X.
OO...X
6 3
X....O
.X...O
..X...
...X..
O...X.
.O....

Output:

Code: Select all

X WINS
ERROR
IN PROGRESS
X WINS
ERROR
IN PROGRESS
O WINS
ERROR
ERROR
DRAW
ERROR
ERROR
IN PROGRESS
ERROR
X WINS
X WINS
ERROR
X WINS
X WINS
ERROR
ERROR
X WINS

Hope it helps

[RC's]

Hi jurajz,
I appreciate your help, my code produced the same result as yours for those input cases, but it still gives me WA.
Here is my code :

Code: Select all

#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

struct cell
{
	int horizontal, vertical, diagonal, antidiagonal;
};

struct pt
{
	int x, y;
};

inline void ins(pt *dst, int idx, int x, int y)
{
	dst[idx].x = x;
	dst[idx].y = y;
}

inline bool ketemu(pt *dst, int m, int x, int y)
{
	for(int i = 0; i < m; i++)
		if(dst[i].x == x && dst[i].y == y)
			return true;
	return false;
}

cell otable[1000][1000], xtable[1000][1000];
char table[1001][1001];	
pt Otemp[1000], Xtemp[1000];

int main()
{
	int cases, n, m, i, j, owins, xwins, filled, n1, maxm, jmlo, jmlx, dif, cellsize, k, found;
	bool error;
	
	freopen("input.txt", "r", stdin);
	
	scanf("%i", &cases);
	while(cases--)
	{
		jmlo = jmlx = owins = xwins = filled = 0;
		error = false;

		scanf("%i %i", &n, &m);		

		cellsize = n * 4 * 4;
		for(i = 0; i < n; i++)
		{
			scanf(" %s ", table[i]);
			memset(otable[i],0,cellsize);
			memset(xtable[i],0,cellsize);
		}

		if(n == 1)
		{
			if(table[0][0] == '.') printf("IN PROGRESS\n");
			else if(table[0][0] == 'O') printf("ERROR\n");
			else if(table[0][0] == 'X') printf("X WINS\n");
			continue;
		}

		//if(m > n) { printf("IN PROGRESS\n"); continue; }	

		n1 = n - 1; // batas tabel
		maxm = 2 * m - 1; // cek panjang maksimum
		for(i = 0; i < n; i++)
		{
			for(j = 0; j < n && !error; j++)
			{				
				if(table[i][j] == 'O') 
				{ 
					jmlo++;
					filled++;
					xtable[i][j].antidiagonal = xtable[i][j].diagonal = xtable[i][j].horizontal =
						xtable[i][j].vertical = 0;
					if(i > 0 && j > 0)
					{
						otable[i][j].diagonal = otable[i-1][j-1].diagonal + 1;
						if(otable[i][j].diagonal > maxm)
							error = true;
					}
					else
						otable[i][j].diagonal = 1;

					if(i > 0 && j < n1)
					{
						otable[i][j].antidiagonal = otable[i-1][j+1].antidiagonal + 1;
						if(otable[i][j].antidiagonal > maxm)
							error = true;
					}
					else
						otable[i][j].antidiagonal = 1;

					if(j > 0)
					{
						otable[i][j].horizontal = otable[i][j-1].horizontal + 1;
						if(otable[i][j].horizontal > maxm)
							error = true;
					}
					else
						otable[i][j].horizontal = 1;

					if(i > 0)
					{
						otable[i][j].vertical = otable[i-1][j].vertical + 1;
						if(otable[i][j].vertical > maxm)
							error = true;
					}
					else
						otable[i][j].vertical = 1;

					if(otable[i][j].vertical == m || otable[i][j].horizontal == m || otable[i][j].diagonal == m ||
						otable[i][j].antidiagonal == m)
					{
						if(owins == 0)
						{
							if(otable[i][j].vertical == m)
							{
								for(k = 0; k < m; k++)
									ins(Otemp, k, j, i-k);
								//ins(Otemp, j, i-m, j, i, 1);
							}
							else if(otable[i][j].horizontal == m)
							{
								for(k = 0; k < m; k++)
									ins(Otemp, k, j-k, i);
								//ins(Otemp, j-m, i, j, i, 2);
							}
							else if(otable[i][j].diagonal == m)
							{
								for(k = 0; k < m; k++)
									ins(Otemp, k, j-k, i-k);
								//ins(Otemp, j-m, i-m, j, i, 3);
							}
							else
							{
								for(k = 0; k < m; k++)
									ins(Otemp, k, j+k, i-k);
							}
								//ins(Otemp, j+m, i-m, j-m, i, 1);
							owins++;
						}
						else
						{
							found = 0;
							if(otable[i][j].vertical == m)
							{
								for(k = 0; k < m; k++)
									if(ketemu(Otemp,m,j,i-k)) { found++; break; }
									//if(find(Otemp.begin(), Otemp.end  Otemp.insert(Otemp.end(), new vector<pt>(j,i-k));
							}
							else if(otable[i][j].horizontal == m)
							{
								for(k = 0; k < m; k++)
									if(ketemu(Otemp,m,j-k,i)) { found++; break; }	
									//Otemp.insert(Otemp.end(), new vector<pt>(j-k,i));
							}
							else if(otable[i][j].diagonal == m)
							{
								for(k = 0; k < m; k++)
									if(ketemu(Otemp,m,j-k,i-k)) { found++; break; }	
									//Otemp.insert(Otemp.end(), new vector<pt>(j-k,i-k));
							}
							else
							{
								for(k = 0; k < m; k++)
									if(ketemu(Otemp,m,j+k,i-k)) { found++; break; }	
									//Otemp.insert(Otemp.end(), new vector<pt>(j+k,i-k));									
							}
							if(found == 0)
								error = true;
						}
					}
				}
				else if(table[i][j] == 'X') 
				{ 
					jmlx++;
					filled++; 
					otable[i][j].antidiagonal = otable[i][j].diagonal = otable[i][j].horizontal =
						otable[i][j].vertical = 0;

					if(i > 0 && j > 0)
					{
						xtable[i][j].diagonal = xtable[i-1][j-1].diagonal + 1;
						if(xtable[i][j].diagonal > maxm)
							error = true;
					}
					else
						xtable[i][j].diagonal = 1;

					if(i > 0 && j < n1)
					{
						xtable[i][j].antidiagonal = xtable[i-1][j+1].antidiagonal + 1;
						if(xtable[i][j].antidiagonal > maxm)
							error = true;
					}
					else
						xtable[i][j].antidiagonal = 1;

					if(j > 0)
					{
						xtable[i][j].horizontal = xtable[i][j-1].horizontal + 1;
						if(xtable[i][j].horizontal > maxm)
							error = true;
					}
					else
						xtable[i][j].horizontal = 1;

					if(i > 0)
					{
						xtable[i][j].vertical = xtable[i-1][j].vertical + 1;
						if(xtable[i][j].vertical > maxm)
							error = true;
					}
					else
						xtable[i][j].vertical = 1;

					if(xtable[i][j].vertical == m || xtable[i][j].horizontal == m || xtable[i][j].diagonal == m ||
						xtable[i][j].antidiagonal == m)
					{
						if(xwins == 0)
						{
							if(xtable[i][j].vertical == m)
							{
								for(k = 0; k < m; k++)
									ins(Xtemp, k, j, i-k);
							}
								//ins(Otemp, j, i-m, j, i, 1);
							else if(xtable[i][j].horizontal == m)
							{
								for(k = 0; k < m; k++)
									ins(Xtemp, k, j-k, i);
							}
								//ins(Otemp, j-m, i, j, i, 2);
							else if(xtable[i][j].diagonal == m)
							{
								for(k = 0; k < m; k++)
									ins(Xtemp, k, j-k, i-k);
							}
								//ins(Otemp, j-m, i-m, j, i, 3);
							else
							{
								for(k = 0; k < m; k++)
									ins(Xtemp, k, j+k, i-k);
							}
								//ins(Otemp, j+m, i-m, j-m, i, 1);
							xwins++;
						}						
						else
						{
							found = 0;
							if(xtable[i][j].vertical == m)
							{
								for(k = 0; k < m; k++)
									if(ketemu(Xtemp,m,j,i-k)) { found++; break; }
									//if(find(Otemp.begin(), Otemp.end  Otemp.insert(Otemp.end(), new vector<pt>(j,i-k));
							}
							else if(xtable[i][j].horizontal == m)
							{
								for(k = 0; k < m; k++)
									if(ketemu(Xtemp,m,j-k,i)) { found++; break; }	
									//Otemp.insert(Otemp.end(), new vector<pt>(j-k,i));
							}
							else if(xtable[i][j].diagonal == m)
							{
								for(k = 0; k < m; k++)
									if(ketemu(Xtemp,m,j-k,i-k)) { found++; break; }	
									//Otemp.insert(Otemp.end(), new vector<pt>(j-k,i-k));
							}
							else
							{
								for(k = 0; k < m; k++)
									if(ketemu(Xtemp,m,j+k,i-k)) { found++; break; }	
									//Otemp.insert(Otemp.end(), new vector<pt>(j+k,i-k));									
							}
							if(found == 0)
								error = true;
						}
					}
				}
			}
		}	

		dif = jmlx - jmlo;
		if(!(dif == 0 || dif == 1))
			error = true;
		if(xwins + owins > 1)
			error = true;

		if(error)
			printf("ERROR\n");
		else if(xwins == 1)
			printf("X WINS\n");
		else if(owins == 1)
			printf("O WINS\n");
		else if(filled == n * n)
			printf("DRAW\n");
		else
			printf("IN PROGRESS\n");
	}

	return 0;
}

Is there anything wrong with it ?

[plamplam]

How to solve this problem? I solved 10363 but I am getting TLE for this one(11623). Please can someone describe an efficient algorithm? I just store the input as a table in a 2D array and compare vertically, horizontally and diagonally to check if the counter reaches/exceeds m. My program can handle critical test cases but TLE

[obelix78]

i'm sorry but what is TLE?

[plamplam]

TLE = Time Limit Exceeded!!! I thought everyone knew what TLE means

[brianfry713]

My program got AC in 0.032 sec.

I use a function isWinner that searches the board until it finds a sequence of length m upon which it returns true, otherwise it returns false if not found. I first use this function to test if X and O are winners. I then handled some ERROR cases. If X is a winner and O isn't, I iterate through the board and remove every X one by one and test to see if that board is still a winner. If there is no single X that can be removed resulting in a non-winning board, then that is an ERROR case. Of course then do the same for O.