## Sunday, September 14, 2014

### UVa Problem 10363 - Tic Tac Toe

Problem:

Solution:

First, we check if the number of pieces make sense. Since 'X' always go first, number of 'X' can only be the same as number of 'O' (if the last move is by 'O') or number of 'O' + 1 (if the last move is by 'X').

If the last move is by 'O', then 'X' cannot win. 'O' can either win or not that does not bother us.

If the last move is by 'X', then 'O' cannot win. 'X' can either win or not that does not bother us too.

That's it. One tiny twist is that we might ask .. is there a possibility that a game is presented to us, we think it is a valid game, but the game can only be terminated before we reach the current state. The answer is no. That can happen only if the game has two ways to win without sharing a piece, but that requires 6 pieces, which we will simply not accept.

With the algorithm, the code isn't hard to right. I am thrilled that it pass on first submit.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1304

#include "UVa10363.h"

#include <iostream>
#include <string>

using namespace std;

char match(char current, char next)
{
if (current == 'u')
{
return next;
}
else if (current == next)
{
return next;
}
else
{
return '.';
}
}

int UVa10363()
{
string dummy;
int number_of_games;
cin >> number_of_games;
getline(cin, dummy);
for (int g = 0; g < number_of_games; g++)
{
string line0;
string line1;
string line2;
getline(cin, line0);
getline(cin, line1);
getline(cin, line2);
getline(cin, dummy);
int x_count = 0;
int o_count = 0;
bool x_win = false;
bool o_win = false;
char b[3][3] = { { line0[0], line0[1], line0[2] } , { line1[0], line1[1], line1[2] }, { line2[0], line2[1], line2[2] }};
for (int row = 0; row < 3; row++)
{
for (int col = 0; col < 3; col++)
{
x_count += b[row][col] == 'X';
o_count += b[row][col] == 'O';
}
}
for (int row = 0; row < 3; row++)
{
char row_char = 'u';
for (int col = 0; col < 3; col++)
{
row_char = match(row_char, b[row][col]);
}
if (row_char == 'X')
{
x_win = true;
}
if (row_char == 'O')
{
o_win = true;
}
}
for (int col = 0; col < 3; col++)
{
char col_char = 'u';
for (int row = 0; row < 3; row++)
{
col_char = match(col_char, b[row][col]);
}
if (col_char == 'X')
{
x_win = true;
}
if (col_char == 'O')
{
o_win = true;
}
}
char slash_char = 'u';
slash_char = match(slash_char, b[0][0]);
slash_char = match(slash_char, b[1][1]);
slash_char = match(slash_char, b[2][2]);
if (slash_char == 'X') { x_win = true; }
if (slash_char == 'O') { o_win = true; }
char back_slash_char = 'u';
back_slash_char = match(back_slash_char, b[0][2]);
back_slash_char = match(back_slash_char, b[1][1]);
back_slash_char = match(back_slash_char, b[2][0]);
if (back_slash_char == 'X') { x_win = true; }
if (back_slash_char == 'O') { o_win = true; }

if (x_count == o_count)
{
cout << (x_win ? "no" : "yes") << endl;
}
else if (x_count == o_count + 1)
{
cout << (o_win ? "no" : "yes") << endl;
}
else
{
cout << "no" << endl;
}
}

return 0;
}