A1017 | Maze Tac Toe--Silver

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!
First, cow tic-tac-toe: instead of placing X's and O's on a $3 \times 3$ grid,
the cows of course play with M's and O's on a $3 \times 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 $i$ and $j$ are each
in the range $1 \ldots 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 \times N$ cells ($3 \leq N \leq 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.

The first line of input contains $N$.
The maze is specified by the next $N$ lines, each containing $3N$ characters.

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'.