Maze Tac Toe USACO 2021 US

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

Weekly Contest 247

Biweekly Contest 55

Codechef Long Challenge Solutions

July Long Challenge 2021 Solutions

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Leave a Comment

Please Click on 1 or 2 Ads to help us run this site.
+