Official Analysis (C++)

Explanation

To simulate Bessie traveling through the maze, we use DFS. During DFS, we keep track of the state of the game board.

If during DFS, we find a move, represented by 'M' or 'O' followed by two numbers representing the coordinate on the moo-tac-toe game board, we update our board as long as the square is empty.

For example, if our board looks like

. M .
. O .
. . .

and we get M22, no update is made. However, if we get O32, our board will be updated to

. M .
. O .
. O .

After updating our board, we check if Bessie has won. We can hard code every winning possibility since there are few cases to check.

During DFS, if we revisit a square in our current board state, we stop iterating. However, if we have visited a square but with a different board state, we can continue iteration.

In order to keep track of which positions we have visited with which board, we can use a three dimensional array. The first two dimensions represent position and the last dimension represents state.

Notice how each square in the board only has three possibilities: blank, O, or M. We can assign blank to 0, O to 1, and M to 2.

Due to there being only three possibilities, we can make the board into a ternary number, e.g.

0 2 0
0 1 0
0 0 0

becomes

020010000

We convert the ternary number into a decimal to assure uniqueness. We only have 9 characters in the board, so the general formula to convert from ternary to decimal is:

for every cell in the board. The biggest number will be $19682$.

We can keep the board as a string to make our implementation more clear and intuitive. This approach will suffice for C++ and Java.

Unfortunately, due to Python's slow nature, this solution must be sped up. We do not keep the board as a string but rather keep it in its ternary form.

To extract a character at index $i$ from the board, we divide by $3^i$ to remove the first $i$ digits and then $$.

To add a new character $c$ at index $i$ with board $b$, we have the following operation:

which effectively adds the character before index $i$, the new character, and the characters after index $i$.

Implementation

Time Complexity: $\mathcal{O}(N^2)$

Copy
#include <bits/stdc++.h>

using namespace std;

struct Point {
	char id;
	int x;
	int y;
};

Copy
import java.io.*;
import java.util.*;

public class MazeTacToe {
	static int[] powThree = new int[9];
	static boolean[][][] visited = new boolean[25][25][19683];
	static Set<String> results = new HashSet<>();
	static Point[][] grid;

	static boolean isWin(String gameStr) {

Copy
import sys

sys.setrecursionlimit(1000000)
input = sys.stdin.readline


def test_win(state):
	cells = [[0] * 3 for _ in range(3)]
	b = state
	for i in range(3):