# Maze Tac Toe

For this solution: http://usaco.org/current/data/sol_prob1_silver_open21.html, can anyone tell me how the beenthere[][][] array keeps track of the state of the board? How does it track a 3x3 grid that has a M or O or empty?

It represents the grid as a base 3 number. For example, if the grid is as follows: ```
0 1 1
2 0 2
0 1 1

``or something, then the base 3 number would be 011202011.``

But how does changing a number from 0 to 1 or 2 work? If it is in base 3? I don’t understand they equation they made to update b in the dfs function.

0 equals no move, 1 equals an M, and 2 equals an O.

I also have one question about the solution: For this solution: http://usaco.org/current/data/sol_prob1_silver_open21.html: it says “board state (converted to an integer)” in the code, I think it is b. But I am not sure how the board state is converted to b?

I think b is calculated inside dfs(), but I am not sure how b is calculated. Thanks a lot.

`b` is calculated as I have said above.
If a board was as follows:

``````.MO
..O
M.M
``````

It would be represented as the base-3 integer `012002101`.