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.

Problem credits: Brian Dean

Problem credits: Brian Dean

The first line of input contains \(N\).

The maze is specified by the next \(N\) lines, each containing \(3N\) 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'.

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.

riseoj 작성

출처 올림피아드 > USACO > 2020-2021 > US Open > Silver