11623 - Tic Tac Toe

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

11623 - Tic Tac Toe

Post by 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
Learning poster
Posts: 69
Joined: Sat Sep 02, 2006 7:30 pm
Location: Slovakia

Re: 11623 - Tic Tac Toe

Post by 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
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 11623 - Tic Tac Toe

Post by 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
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11623 - Tic Tac Toe

Post by 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 :( :x
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

obelix78
New poster
Posts: 1
Joined: Wed Sep 07, 2011 1:51 pm

Re: 11623 - Tic Tac Toe

Post by obelix78 »

i'm sorry but what is TLE?

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11623 - Tic Tac Toe

Post by plamplam »

TLE = Time Limit Exceeded!!! I thought everyone knew what TLE means :(
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11623 - Tic Tac Toe

Post by 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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 116 (11600-11699)”