Tic Tac Toe (1)
Problem Number:
10 363
Type of Problem:
Problem Category:
Input:
Random Input
Critical Input
0
Critical Input:
500
.OX
...
...
OX.
.XX
O.X
O.O
XO.
XO.
..O
XOX
OOX
OX.
O.O
O.O
XXO
XOX
XX.
.XX
OXX
.OO
XXX
O.O
OXX
X.X
...
XXO
OXO
X.X
OOX
O..
O..
..O
XO.
.OO
.XO
.OX
O.X
..O
.O.
OOO
XX.
X.O
.X.
OXO
OX.
XXX
X..
.O.
X.O
XX.
.O.
.O.
OO.
O.X
.OO
OX.
.OO
.XX
OO.
X.X
X.O
.OX
.XO
.O.
OXO
..O
.OX
XXX
X..
OX.
.XO
OOX
.OX
OOO
O..
..O
OOX
.OX
XX.
..X
.OO
XXX
XXO
X.X
.XX
OX.
XOO
XOX
O.O
..O
..X
O.O
OO.
X.O
OX.
.OX
OX.
XXO
.XX
X..
...
XOX
OXO
..X
XXX
O.X
OOO
OXO
..O
XXO
XXO
XX.
XXX
OX.
XX.
O..
.O.
XX.
X..
.X.
OOX
.OO
OX.
.O.
..O
..X
.O.
OX.
OX.
X..
XXO
O.O
XOO
XOX
XOX
.X.
..O
.OO
.XO
XO.
X..
.XX
XO.
O.O
OX.
..X
..X
OX.
XXX
XX.
.OO
.X.
.OO
XXO
O..
...
.OO
.X.
.OX
XOO
.X.
OXX
XO.
.O.
OX.
X..
..X
...
O.X
.X.
OXX
OOX
XXO
...
.OO
..X
O.X
.OX
OXX
.XO
O.O
OOX
.OO
XOO
OXX
..X
XO.
OXO
.XO
X..
O.O
.XO
XX.
O.X
OXO
OXO
OO.
OXO
X.O
..O
.OX
.O.
XO.
.OO
X..
OOX
XO.
X.X
OXX
.XO
...
.OX
.OX
...
O..
OOX
..O
OX.
..X
X.X
O.X
XO.
.OO
XOX
..X
OOX
.O.
.XX
OXX
OXX
O..
.XO
O.X
O..
..X
XOO
OOX
OXO
..O
XX.
O..
OO.
XO.
...
OO.
O.X
OX.
O..
...
OX.
OO.
X.O
O.X
XO.
XOO
...
XX.
XX.
X..
...
XXX
..X
OXX
OO.
OOX
O.O
XX.
XX.
OOX
XO.
O.X
O.X
.OO
XX.
.X.
OOO
..O
.X.
.OO
.XX
.O.
.XO
XXX
OX.
.O.
.XO
XXO
..O
OOO
XO.
XXO
.XO
.OX
XXX
.X.
...
OX.
.XX
OXO
XXX
XOO
OXO
XXX
X..
.O.
O.X
.XX
.XO
..O
..O
XXX
OO.
OO.
.XO
O.O
.OX
.OX
.OO
OOX
XXX
XOX
XOO
.XO
X..
.OO
XOX
OX.
.XX
XX.
OXO
.X.
X.O
..O
O.O
X.X
..O
XO.
XO.
O..
XOO
OO.
..O
XOO
XOX
O.X
.XO
XX.
.OO
..X
XX.
OXO
X.X
.X.
OXX
..O
XOO
O..
O.X
...
X.X
XOX
OOX
.OO
...
X.X
OX.
XO.
.X.
.X.
.X.
O.X
OX.
.XO
OXO
OXO
OX.
.XO
OOO
OOO
O..
XXO
OOX
OXX
.OO
OOO
...
..O
XX.
..X
XX.
OX.
X.O
XX.
OX.
.OX
..X
OOX
XXO
..O
OO.
X.O
O.X
.XO
...
O.X
.OX
XXX
X.X
.O.
O.O
XOX
O.O
...
OOO
XOX
OX.
.XO
XOX
XO.
X.X
.XO
X.X
O..
OXX
XOO
O.X
..X
O.X
O.O
OOO
OO.
.OO
.OO
..O
OX.
XXX
X..
.X.
...
OXX
XX.
..O
.XX
XXX
XOO
X.O
XXO
X.O
XOO
XX.
OX.
XO.
.XX
.OX
OOX
...
OX.
.XX
OOO
..X
OOX
O..
O.X
...
.XX
.XX
..O
XO.
X.O
..O
.O.
OXO
XOO
OO.
OOX
O.O
XOX
OOX
O.X
X.X
O.O
XX.
X.O
.O.
O.X
.O.
OO.
.XO
.XO
XXO
O.X
XX.
.XO
XO.
...
XOX
XXX
.XX
X.X
.X.
XOO
OOO
XXX
.OO
.OO
O.O
O.O
O.O
XX.
OX.
XO.
.XO
OOX
.XO
O.X
.X.
XX.
...
O.X
X.X
O.X
O.X
.O.
.OX
..X
.OO
...
...
OX.
OOO
XX.
XO.
OXO
OO.
.XO
X.X
...
.O.
O.X
OO.
XO.
X.X
..O
OX.
X.X
.XX
.X.
X.X
.OX
X.X
.X.
OX.
.XO
.O.
O..
XO.
X..
XX.
O.X
XOO
XXO
.XX
.XX
O..
O..
X.O
X.X
OXO
X.X
...
O.X
..O
..O
OXO
OOX
X.X
OO.
..X
XXX
.X.
.O.
...
O.O
XXX
.OO
X..
XOX
X.X
OXO
O..
O.O
O.X
O.X
..O
X.X
...
.XO
XXX
X.O
OOO
OOO
X..
OXO
.OO
OOX
OOX
OXX
.OX
OOX
.OX
O.O
XXX
...
OOO
...
.O.
..X
XX.
OOO
.O.
X..
OX.
.X.
OOO
.OO
XOX
.O.
XOX
.X.
OXX
XXO
X..
OOX
XO.
.O.
O.X
O..
OXX
XXO
.OO
XX.
.OO
OXO
.OX
XOO
.X.
.OO
.OO
XO.
OXO
OO.
XOO
XOO
OXX
.OX
OXX
XOX
.XO
OOX
OOX
X.X
XXO
OX.
O.O
.OX
.X.
XXX
OXO
.XX
.OO
X.O
OXO
O..
XO.
.OO
XO.
..X
XXO
.X.
XXX
OOX
XXO
.OX
.X.
O.O
.XX
.XX
XOX
.O.
OO.
.OO
.O.
OOX
.XX
..O
O.O
O.X
OXO
XXX
X.X
.OO
O.X
XX.
X.X
..X
XXX
.XX
.OO
..O
X.O
X..
.OO
XO.
X..
OOX
..X
..X
X.X
O.X
XXO
OOO
OO.
XOO
X.X
.XX
...
O..
..X
XOX
O.O
.OX
OXO
XOX
OO.
.OX
X.O
OOX
XXO
OOX
XXO
OX.
OOX
..O
XOX
.OX
O..
.XO
XOO
OOX
XOO
O.O
O.X
X.X
.XO
XXO
XOX
XOX
O.O
XO.
..X
XOO
XXO
XXX
..X
OX.
.OX
..X
XXX
..O
.O.
OOX
.OX
XXO
O..
.OX
OO.
.XO
XOX
XO.
XXX
.O.
.OO
O..
XO.
XOX
OXO
OXX
XO.
X.O
X.O
O.O
OXX
X.X
.X.
.OX
.XO
.OO
.OX
.XX
XXX
..X
XOO
.OX
.OO
.X.
XX.
O.X
X.X
O.X
O.O
O.O
.X.
O.O
...
OOX
XO.
XX.
OOX
...
.O.
O..
XX.
XO.
OOO
..O
XX.
XXO
XX.
X.O
.XX
...
O.X
.X.
O.O
X.O
OXO
.O.
O.X
X.X
..X
.X.
..X
XOX
XXX
.O.
XXX
OX.
OOO
O.O
.OO
XOO
XO.
O.X
OXO
..X
..O
XX.
..O
XOO
.XX
OO.
X.O
.OX
O.O
..X
X..
O.X
O..
OXO
.X.
X.O
..O
OX.
OOX
.O.
XOO
.XO
XXO
XO.
OOX
.O.
XOX
X.X
...
..X
XX.
OX.
XOX
..O
.O.
.XO
X.X
X..
O..
XX.
OXX
XOX
XX.
O..
XOX
XO.
O.O
O.O
OOX
.OX
.XX
.OX
XOX
XX.
.O.
XOO
.XX
O..
.OX
XX.
O..
.OO
.X.
.XO
XXX
.O.
XO.
X..
X.X
OXO
X.O
X.O
O.O
O.O
XX.
XXX
.O.
...
..O
OOX
XO.
O.O
.OO
OXO
OO.
X..
.XX
.X.
.X.
OOX
OO.
OXO
XXX
O.X
XX.
...
O.X
.OX
OXO
XX.
OOO
XX.
.OX
X..
OOO
OXO
O.X
O..
XOO
O.O
O..
X.X
XX.
XXO
OO.
.OO
O.O
O.X
X..
OX.
X..
XXO
OXO
X.X
.X.
XXX
OOX
.XX
XO.
XO.
XO.
.OX
XXO
XOX
X.O
...
OOO
.XO
.XX
OXO
XX.
XX.
XOX
...
X.O
..O
OX.
X.X
.OO
XXX
OOO
.O.
.XX
X.X
XXX
O..
X.O
.XO
X.O
.OO
.XX
X.X
..X
XXX
XXX
XXO
OOX
XOO
O.O
XO.
XOX
X.X
X.O
OOO
.O.
XXX
...
..O
OOX
..X
..O
XXO
X.O
OX.
XXO
XO.
OXO
XXX
OOX
.X.
.X.
OO.
X.O
.OX
O.X
XXO
XO.
OX.
XOX
XOO
XOX
XXO
XXO
..X
XOX
O.O
..X
..X
OXX
.OO
O.O
..O
...
X..
O.O
.XX
OXO
.XO
XO.
OOX
OO.
.X.
X..
XX.
...
X.O
XX.
.XX
X..
.X.
XOX
XXX
.OX
.OO
.XX
.OX
XX.
O..
.O.
.OX
O..
O.X
XX.
OXO
X..
OOO
.X.
...
O.X
OO.
.OO
OXO
.XO
..O
X.O
XOO
.OO
OXO
O.X
.O.
OOX
XXO
XX.
O..
OX.
.OO
XO.
.OX
OXO
O.X
O..
.XX
XXX
XXO
XOO
.OX
OX.
O.X
X.X
.XX
...
..X
XXO
.OO
XOX
..X
XOX
X.X
XX.
O.O
OXX
.XX
XO.
OXX
OOX
OX.
OXX
.XX
XO.
.X.
XX.
..O
X..
.OX
X..
OO.
OXO
OX.
.X.
.X.
...
..O
X.O
X.X
XX.
..O
XX.
O.X
X.O
..O
XOO
.OX
..X
XXX
OOO
OOX
..X
.X.
X.O
O.O
OXX
.X.
OX.
.X.
..O
OOO
OOX
...
...
O.O
XX.
XXX
.OX
.OO
.XX
X..
OXO
XXX
...
OO.
X..
X.O
OXX
O..
X.X
OXX
O.O
XX.
X..
XOO
XXX
XXO
O..
XO.
.O.
.OX
XX.
.XX
.OX
OOX
O.X
.XX
O.X
X..
X.O
.XX
XXX
..O
XO.
.O.
.XO
.X.
X.X
OX.
OX.
XX.
OXX
.OX
O..
XOO
XO.
.XX
..X
.OX
...
.X.
.OO
.OX
X..
OX.
XOX
XO.
XX.
XXX
OXX
XXX
OXX
.XO
.OO
...
..O
XX.
XOO
...
.OX
XOX
X.X
X.X
...
O..
OOX
..X
XX.
..O
O..
O..
.OO
XO.
O.O
OXX
X.X
O.X
.XO
O.O
XOO
OXO
X..
...
OXO
X..
OO.
...
OO.
XX.
O.O
XXO
XOO
XOX
.XO
OO.
OXX
OX.
X..
X.X
XO.
O.X
XX.
OXO
OXO
X..
.OX
X.X
OXX
XX.
OOO
..O
..O
.XO
X..
.OX
.OO
...
OXX
OOO
.X.
X.X
.XX
XX.
.O.
XXX
XX.
.XO
.O.
XOX
.XX
.OO
.OO
O.O
XOX
..O
OXO
XXO
.XO
OXX
.XO
.XX
OXO
.OX
O..
OX.
.O.
O.X
OOO
...
X.X
O.X
OOO
.XX
.XX
OOX
O..
OXO
.O.
XO.
XOO
O.O
.O.
XXX
XXX
.XX
.OX
.XX
XXX
OO.
X.O
XXO
O.O
OX.
OOX
XXO
OOX
OO.
O..
.XO
..O
O..
XOX
OXO
O..
..O
OX.
OOX
OO.
OOO
XOX
..X
OO.
O..
.OO
XO.
O..
O..
.XO
...
XXO
O.O
.X.
OXX
O.O
XXO
XOX
.XX
...
X..
XX.
.XO
X..
XO.
XXX
.OX
XOX
.OX
.OO
..O
OXO
O.O
XX.
XXX
XOO
OOX
..O
XOX
O..
.O.
XO.
X..
OX.
XOO
OO.
XXO
OXO
.X.
XOO
..O
O..
O.O
X..
XXX
OX.
.O.
O.X
.OX
X..
.OO
XX.
XO.
..O
OXX
X.X
...
.OO
.OX
X.X
XXO
.XX
...
O..
OXX
OXX
.XO
OX.
..O
.XO
.OO
.O.
XXO
.OO
...
.OX
OX.
...
..X
XXX
.X.
O.X
O.X
XXX
..X
.X.
XOX
XOO
XXX
XOX
OOO
Random Input:
8
XX.
XX.
OOO
XX.
...
OOO
OX.
OX.
OX.
X..
OXO
OXX
X..
OXO
O.X
XXO
.OX
O..
XXO
.OX
O.X
XXX
X00
...
Problem Description Link:
Problem Analysis Link:
Problem Id:
10363
