10363 - Tic Tac Toe

[soyoja]

I don't know about this problem.

I think that I check only current tic-tac-toe status, and

if current status is correct ( i.e number of 'O' is equal or

one less than 'X' . if X is win then number of O is one less

than X, etc. ) then I print "yes".

But I receive "wrong answer". I'm really want to know about

solution. Anyone give me some hints?

[Ivan Golubev]

Generate all possible states with BFS and compare with your current solution.

[..]

At first I try to use the condition to check, but failed.
But after reading your post, I find what condition I missed.

Here is the condition I check:
The numebr of X and O
no 2 people win same time
If anyone win at 2 different rows(columns) same time
If anyone win, check with the number of both sides.

[Yarin]

An analytic solution can be made a bit simplier than that:

* Calc number of X, and O's and abort if invalid count
* If anyone has three-in-a-row, make sure it's possible to remove an X (or O, depending on who made the last move), so that there will no longer be any three-in-a-row on the board

[arc16]

If anyone win at 2 different rows(columns) same time

i think we should not worry about that, at least my solution doesn't

[Ghost77 dimen]

[color=red]
One line of the problem's context is as follows:
Whenever X or O plays we fill in an X or an O in the "appropriate" position.

What is the word,"appropriate",means?
Is unoccupied or best way to win?

In such situation,what should be printed in the follow input case?
XOX
OXO
XOX
[/color]

[Adrian Kuegel]

"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."
I think that this means that not all moves has to be optimal, only each move has to be valid.
If you count the number of "X" and "O", it is sufficient to check if there is one winning position for "X" or for "O". It is only possible for "X" to have two winning positions like:
XXX
XOO
XOO
In these cases one can assume that the last "X" is placed at the position where the two rows/columns/diagonals intersect.

[mido]

Semi-Spoiler:

What should be the status of the board if :

If x wins.
If o wins.
If neither win.
If both win???...can't happen..

Think and good luck.

[Ghost77 dimen]

Tkanks for your helpful advise.mido.

I solve this problem during 0.00 second.

[henar2]

Thank you Mido.
You have given good hints.

[henar2]

Thank you Mido.
You have given good hints.

[soyoja]

Anyway, I finally know the solution.

In this problem, there are some obvious keys.

1) All of the input case is 3*3, consist of valid character.

2) So we should check whether current input status is valid or not.

3) Therefore, we count current number of O and X, and check

if O is win or X is win. ( As above article said that if current game

status is last one, then X can doubled in a row status. )

4) If current status is not last one, then O is equal or one less than

number of X.

So we should only
i)count X and O's number
ii) X is win or O is win.

It's sufficient to solve this poroblem.

[mido]

You're very welcom..

[deddy one]

What I do is just like this

1. count the number of valid O and X overall
2. count the number of valid O and X if O win
3. count the number of valid O and X if X win
4. count the number of valid O and X if neither win

and it's accepted, but PE, I'm confused , where should I put the extra
blank line in this problem??????

[Rajputro]

What is valid O/X?

Can there be invalid inputs??

I've got w/a .
Does X always starts?
Need some critical inputs.
Thank you.