8121: USACO 2021 US Open, Silver Problem 1. Maze Tac Toe
[Creator : ]
Description
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×3 grid, the cows of course play with M's and O's on a 3×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…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×N cells (3≤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.
To challenge Bessie, Farmer John has designed a square maze consisting of a grid of N×N cells (3≤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
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'.
Output
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 1 Input
7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################
Sample 1 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).