P7555 [USACO21OPEN] Maze Tac Toe S

The cow Bessie likes playing maze-walking games. She also likes playing tic-tac-toe (more precisely, a cow version of tic-tac-toe, described below). Farmer John has found a brand-new way for her to play both games at the same time. First, cow tic-tac-toe: instead of placing `X` and `O` on a $3 \times 3$ board, cows of course place `M` and `O` on a $3 \times 3$ board. On a player's turn, the player may choose to place either an `M` or an `O` in any empty cell (this is another difference from standard tic-tac-toe, where one player always places `X` and the other always places `O`). The winner of cow tic-tac-toe is the first player to spell `MOO`, which may appear in a row, a column, or a diagonal. Spelling it backwards also counts; for example, a player also wins by forming `OOM` in a row. Just like standard tic-tac-toe, it is possible that no player wins in the end. A move in cow tic-tac-toe is usually written using 3 characters, `Mij` or `Oij`, where $i$ and $j$ are in the range $1 \ldots 3$, indicating the row and column where the `M` or `O` is placed. To make things more challenging for Bessie, Farmer John designed a square maze consisting of $N \times N$ cells ($3 \leq N \leq 25$). Some cells, including all boundary cells, contain huge haybales, so Bessie cannot move onto those cells. Bessie can move freely among all other cells in the maze in the four directions north, south, east, and west. Some cells contain a sheet of paper with a cow tic-tac-toe move written on it. As Bessie moves through the maze, whenever she is standing on such a cell, she must perform the corresponding move in the cow tic-tac-toe game that is being played at the same time as she moves through the maze (unless the corresponding cell in the cow tic-tac-toe board is already filled, in which case she does not make a move). There is no opponent player in the cow tic-tac-toe game, but some cells in the maze may be unfavorable for her to eventually form `MOO`. If Bessie stops the cow tic-tac-toe game immediately upon winning, compute the number of distinct winning board states that she can achieve by moving through the maze in some suitable way.

The first line contains $N$. The next $N$ lines each contain $3N$ characters describing the maze. Each cell is represented by 3 characters: `###` represents a wall, `...` represents an empty cell, `BBB` represents the (non-wall) cell where Bessie starts, or a cow tic-tac-toe move, representing a (non-wall) cell where Bessie must perform the corresponding move. Exactly one cell is `BBB`.

Output the number of distinct winning cow tic-tac-toe board states (possibly $0$) that Bessie can produce by moving through the maze and stopping immediately upon winning.

#### Sample Explanation In this sample, Bessie can end up achieving $8$ different winning board states: ```plain O.M .O. MOM O.. .O. .OM O.M .O. .OM O.. .O. MOM O.. ... OOM ..M .O. OOM ... .O. OOM ... ... OOM ``` One of these cases is explained below: ```plain O.. ... OOM ``` Here, Bessie can first move to the `O11` cell, then move downward and pass through `O32`, `M33`, and `O31`. At this point the game ends because she has won (for example, she can no longer go to the `M11` cell north of her current `O31` cell). #### Note Problem by: Brian Dean Translated by ChatGPT 5