Page Contents

*Maze Tac Toe USACO*

*Maze Tac Toe USACO*

Bessie the cow enjoys solving mazes. She also enjoys playing tic-tac-toe (or rather, the cow version of tic-tac-toe, described shortly). Farmer John has found a new way for her to play both games at the same time!

See Also : USACO 2021 Challenges

First, cow tic-tac-toe: instead of placing X’s and O’s on a 3×33×3 grid, the cows of course play with M’s and O’s on a 3×33×3 grid. During one’s turn, one can place either an ‘M’ or an ‘O’ on any empty grid cell (this is another difference from standard tic-tac-toe, where one player always plays ‘X’ and other other always plays ‘O’). The winner of cow tic-tac-toe is the first player to spell ‘MOO’, either horizontally, vertically, or diagonally. Backwards is fine, so for example a player could win by spelling ‘OOM’ across one row of the board. Just as in standard tic-tac-toe, it is possible to reach a board state where no winners occur. A move in cow tic-tac-toe is usually specified by 3 characters, either ‘Mij’ or ‘Oij’, where ii and jj are each in the range 1…31…3 and specify the row and column in which to place the corresponding ‘M’ or ‘O’.

To challenge Bessie, Farmer John has designed a square maze consisting of a grid of N×NN×N cells (3≤N≤253≤N≤25). Some cells, including all of the border cells, contain large haybales, preventing Bessie from moving onto any such cell. Bessie can move freely among all the other cells in the maze, by taking steps in the 4 usual directions north, south, east, and west. Some cells contain a piece of paper on which a move in cow tic-tac-toe is written. While Bessie moves around in the maze, any time she steps on such a cell, she must make the corresponding move in a game of cow tic-tac-toe that she is simultaneously playing while she moves through the maze (unless the corresponding cell in the cow tic-tac-toe game is already occupied, in which case she takes no action). She has no opponent in this game of cow tic-tac-toe, but some of the cells in the maze may be adversarial to her goal of eventually spelling ‘MOO’.

If Bessie stops playing cow tic-tac-toe immediately upon winning, please determine the number of distinct winning tic-tac-toe board configurations she can possibly generate by moving appropriately through the maze.

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains NN.

The maze is specified by the next NN lines, each containing 3N3N characters. Each cell described by a block of 3 characters, which is either ‘###’ for a wall, ‘…’ for an empty space, ‘BBB’ for a non-wall containing Bessie, and a cow tic-tac-toe move for a non-wall cell that forces Bessie to make the corresponding move. Exactly one cell will be ‘BBB’.

#### OUTPUT FORMAT (print output to the terminal / stdout):

Please print the number of distinct winning cow tic-tac-toe board configurations (possibly 0) that Bessie can generate via movement in the maze, stopping after she wins.

#### SAMPLE INPUT:

7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### #####################

#### SAMPLE OUTPUT:

8

In this example, there are 8 possible winning board configurations that Bessie can ultimately reach:

O.M .O. MOM O.. .O. .OM O.M .O. .OM O.. .O. MOM O.. ... OOM ..M .O. OOM ... .O. OOM ... ... OOM

To explain one of these, take this case:

O.. ... OOM

Here, Bessie might first visit the O11 cell, then move to the lower corridor visiting O32, M33, and O31. The game then stops, since she has won (so for example she would not be able to visit the M11 cell north of her current position on the O31 cell).

*Problem credits: Brian Dean*

For Bessie to have an attainable winning tic-tac-toe board configuration, she must do so through a sequence of movements and encountering pieces of paper. Key to this problem is conceptualizing a “state” that encompasses Bessie’s situation at any point in time in such a process.

One aspect of Bessie’s state would be what her current tic-tac-toe board looks like. However, there may be multiple positions in the maze Bessie could be at with a particular board state (which may affect the potential board states she could later reach).

Another aspect of Bessie’s state would be her position in the maze. However, there could be multiple board states Bessie could have when she is at a particular position in the maze.

Fortunately, when we combine both of these pieces of information, this perfectly encapsulates Bessie’s state in the process. Our goal is to first figure out which states Bessie could possibly reach, and then how many distinct winning tic-tac-toe board configurations are there such that Bessie can reach a state with that board configuration.

To find all states Bessie can reach, we can use a depth first search (DFS) starting at Bessie’s starting position in the maze and an empty tic-tac-toe board. From each state, we can try recursing a further level by trying to move in each possible direction in the maze. To make sure our DFS does not take very long, we will keep track of which states we have visited so we do not need to revisit them (e.g. we can have a boolean array that indicates whether or not we have visited each state). Note that if we use a set to keep track of these states, this might cause a solution to exceed the time limit of some test cases. Instead, for example, we can convert our board state to a number and have a 3-dimensional visited array with dimensions for Bessie’s row, column, and board state (converted to an integer). Since there are 252252 possible locations in the maze and ≤39≤39 possible board states, our number of states is bounded by 252×39252×39.

Our depth first search will enable us to determine exactly which states Bessie could obtain, and then we can finally count the number of distinct winning boards among boards where there is some state such that Bessie could have that board.

*Brian Dean’s code:*

#include <cstdio> #include <set> using namespace std; int N; char board[25][25][3]; set<int> answers; bool beenthere[25][25][19683]; int pow3[10]; bool test_win(int b) { int cells[3][3]; for (int i=0; i<3; i++) for (int j=0; j<3; j++) { cells[i][j] = b%3; b /= 3; } for (int r=0; r<3; r++) { if (cells[r][0] == 1 && cells[r][1] == 2 && cells[r][2] == 2) return true; if (cells[r][0] == 2 && cells[r][1] == 2 && cells[r][2] == 1) return true; } for (int c=0; c<3; c++) { if (cells[0][c] == 1 && cells[1][c] == 2 && cells[2][c] == 2) return true; if (cells[0][c] == 2 && cells[1][c] == 2 && cells[2][c] == 1) return true; } if (cells[0][0] == 1 && cells[1][1] == 2 && cells[2][2] == 2) return true; if (cells[0][0] == 2 && cells[1][1] == 2 && cells[2][2] == 1) return true; if (cells[2][0] == 1 && cells[1][1] == 2 && cells[0][2] == 2) return true; if (cells[2][0] == 2 && cells[1][1] == 2 && cells[0][2] == 1) return true; return false; } void dfs(int i, int j, int b) { if (beenthere[i][j][b]) return; beenthere[i][j][b] = true; if (board[i][j][0]=='M' || board[i][j][0]=='O') { int r = board[i][j][1]-'1', c = board[i][j][2]-'1', idx = r*3+c; int current_char = (b / pow3[idx]) % 3; if (current_char == 0) { int new_char = board[i][j][0]=='M' ? 1 : 2; b = (b % pow3[idx]) + new_char * pow3[idx] + (b - b % pow3[idx+1]); if (!beenthere[i][j][b] && test_win(b)) { answers.insert(b); return; } beenthere[i][j][b] = true; } } if (board[i-1][j][0] != '#') dfs(i-1,j,b); if (board[i+1][j][0] != '#') dfs(i+1,j,b); if (board[i][j-1][0] != '#') dfs(i,j-1,b); if (board[i][j+1][0] != '#') dfs(i,j+1,b); } int main(void) { int bess_i, bess_j, bstate = 0; pow3[0] = 1; for (int i=1; i<=9; i++) pow3[i] = pow3[i-1]*3; scanf ("%d", &N); for (int i=0; i<N; i++) for (int j=0; j<N; j++) { scanf (" %c%c%c", &board[i][j][0], &board[i][j][1], &board[i][j][2]); if (board[i][j][0] == 'B') { bess_i = i; bess_j = j; } } dfs(bess_i, bess_j, bstate); printf ("%d\n", (int)answers.size()); }

*USACO 2021 February Contest*

*USACO 2021 February Contest*

*Clockwise Fence USACO 2021 February Contest**Just Green Enough USACO 2021 February Contest**Year of the Cow USACO 2021 February Contest**Comfortable Cows USACO 2021 February Contest**Count the Cows USACO 2021 February Contest**Modern Art 3 USACO 2021 February Contest**Stone Game USACO 2021 February Contest**Counting Graphs USACO 2021 February Contest**Minimizing Edges USACO 2021 February Contest**No Time to Dry USACO 2021 February Contest**Maze Tac Toe USACO 2021 US**Balanced Subsets USACO 2021 US**Routing Schemes USACO 2021 US**United Cows of Farmer John USACO 2021 US*

*Weekly Contest 247*

*Weekly Contest 247*

- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony

*Biweekly Contest 55*

*Biweekly Contest 55*

- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System

*Codechef Long Challenge Solutions*

*Codechef Long Challenge Solutions*

*July Long Challenge 2021 Solutions*

*July Long Challenge 2021 Solutions*

*Maximum Production**Relativity**XxOoRr**Optimal Denomination**K Path Query**Chef vs Bharat**Chef and Pairs**Even Odd Partition**Dakimakura Distribition**Madoka and Ladder Decomposition*

*June Long Challenge 2021 Solutions*

*June Long Challenge 2021 Solutions*

*Maximum Frequent Subarray Sum solution codechef**Dual Distance solution codechef**Optimal Xor Set solution codechef**Minimum Subtree Cover solution codechef**Minimum Dual Area solution codechef**Bitwise Tuples solution codechef**Shortest Route solution codechef**Bella ciao solution codechef**Summer Heat solution codechef*

*March Long Challenge 2021 Solutions*

*March Long Challenge 2021 Solutions*

*An Interesting Sequence ISS SOLUTION**Tree House THOUSES SOLUTION**Valid Paths VPATH SOLUTION**Modular Equation MODEQ SOLUTION**Tic Tac Toe TCTCTOE SOLUTION**Xor Equality XOREQUAL SOLUTION**Golf LKDNGOLF SOLUTION**Solubility SOLBLTY SOLUTION*

*April Long Challenge 2021 Solutions*

*April Long Challenge 2021 Solutions*

*Chef and Dice SDICE Solution**Worthy Matrix KAVGMAT Solution**Binary String MEX MEXSTR Solution**Boolean Game BOOLGAME Solution**Tree Permutations TREEPERM Solution**Destroy the EMP Chip CHAOSEMP Solution**Chef and Pair Flips PAIRFLIP Solution**String Power STRPOW Solution**Brahma and Shiva SHRINES Solution**Water Sort Puzzle (Challenge) WTRSORT Solution**World Record BOLT Solution**Strong Language SSCRIPT Solution**Valid Pair SOCKS1 Solution*

*February Long Challenge 2021*

*February Long Challenge 2021*

- 1. Frog Sort Solution Codechef
- 2. Chef and Meetings Solution Codechef
- 3. Maximise Function Solution Codechef
- 4. Highest Divisor Solution Codechef
- 5. Cut the Cake Challenge Solution Codechef
- 6. Dream and the Multiverse Solution Codechef
- 7. Cell Shell Solution Codechef
- 8. Multiple Games Solution Codechef
- 9. Another Tree with Number Theory Solution Codechef
- 10. XOR Sums Solution Codechef
- 11. Prime Game Solution CodeChef
- 12. Team Name Solution Codechef

*January Long Challenge 2021*

*January Long Challenge 2021*

**Chef and Division 3 DIVTHREE SOLUTION Code Chef****Encoded String DECODEIT SOLUTION Code Chef****Point Of Impact BILLRD SOLUTION Code Chef****Fair Elections FAIRELCT SOLUTION Code Chef****Watching CPL WIPL SOLUTION Code Chef****Chef and Ants ANTSCHEF SOLUTION Code Chef****Blackjack BLKJK SOLUTION Code Chef****And-Or Game ORAND SOLUTION Code Chef****Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef****Expected Number of SCCs RCTEXSCC SOLUTION Code Chef****Curious Matrix CURMAT SOLUTION Code Chef****Cool Subsets COOLSBST SOLUTION Code Chef****Sequence Creation ARCRT SOLUTION Code Chef****Greedy Students GRDSTD SOLUTION Code Chef**

*November Challenge 2020 SOLUTION CodeChef*

*November Challenge 2020 SOLUTION CodeChef*

- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID

*October Lunchtime 2020 CodeChef SOLUTIONS*

*October Lunchtime 2020 CodeChef SOLUTIONS*

- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP