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