Maze Tac Toe

Problems and Contests
#1

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?

#2

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.
#3

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.

#4

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

#5

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.

#6

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.