Maze Tac Toe

Solución en video

Por Ruben Jing

Nota: la solución en video puede no ser la misma que las demás soluciones. Código en C++, Python y Java.

Solución

Explicación

Para simular a Bessie recorriendo el laberinto, usamos DFS. Durante la DFS, llevamos el estado del tablero de juego.

Si durante la DFS encontramos un movimiento, representado por ‘M’ u ‘O’ seguido de dos números que representan la coordenada en el tablero de moo-tac-toe, actualizamos el tablero siempre que la casilla esté vacía.

Por ejemplo, si nuestro tablero se ve así


. M .
. O .
. . .

y obtenemos M22, no se hace ninguna actualización. Sin embargo, si obtenemos O32, nuestro tablero se actualizará a


. M .
. O .
. O .

Después de actualizar el tablero, comprobamos si Bessie ha ganado. Podemos hardcodear cada posibilidad ganadora ya que hay pocos casos que comprobar.

Durante la DFS, si revisitamos una casilla en nuestro estado actual del tablero, dejamos de iterar. Sin embargo, si hemos visitado una casilla pero con un estado distinto del tablero, podemos continuar la iteración.

Para llevar qué posiciones hemos visitado con qué tablero, podemos usar un arreglo tridimensional. Las dos primeras dimensiones representan la posición y la última representa el estado.

Nótese que cada casilla del tablero solo tiene tres posibilidades: vacía, O o M. Podemos asignar vacío a 0, O a 1 y M a 2.

Como solo hay tres posibilidades, podemos convertir el tablero en un número ternario, p. ej.


0 2 0
0 1 0
0 0 0

se convierte en

020010000

Convertimos el número ternario a decimal para garantizar unicidad. Solo tenemos 9 caracteres en el tablero, así que la fórmula general para pasar de ternario a decimal es:

\text{board[row][column]} \times 3^{3 \times \text{row} + \text{column}}

para cada celda del tablero. El número más grande será $19682$ .

Podemos mantener el tablero como un string para que la implementación sea más clara e intuitiva. Este enfoque basta para C++ y Java.

Lamentablemente, por la naturaleza lenta de Python, esta solución hay que acelerarla. No mantenemos el tablero como string sino en su forma ternaria.

Para extraer un carácter en el índice $i$ del tablero, dividimos por $3^i$ para quitar los primeros $i$ dígitos y luego $%3$ .

Para añadir un carácter nuevo $c$ en el índice $i$ con tablero $b$ , tenemos la siguiente operación:

b = (b \% 3^i) + c \times 3^i + (b - b \% 3^{i + 1})

que efectivamente añade el carácter antes del índice $i$ , el carácter nuevo y los caracteres después del índice $i$ .

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++JavaPython


#include <bits/stdc++.h>
 
using namespace std;
 
struct Point {
	char id;
	int x;
	int y;
};
 
vector<vector<Point>> grid(25, vector<Point>(25));
bool visited[25][25][19683];
set<string> res;
int powThree[9];
 
bool isWin(string &gameStr) {
	// caso 1: diagonal
	if (gameStr[0] == 'M' && gameStr[4] == 'O' && gameStr[8] == 'O') return true;
	if (gameStr[2] == 'M' && gameStr[4] == 'O' && gameStr[6] == 'O') return true;
 
	if (gameStr[0] == 'O' && gameStr[4] == 'O' && gameStr[8] == 'M') return true;
	if (gameStr[2] == 'O' && gameStr[4] == 'O' && gameStr[6] == 'M') return true;
 
	// caso 2: filas 1, 2, 3
	for (int i = 0; i < 9; i += 3) {
		if (gameStr[i] == 'M' && gameStr[i + 1] == 'O' && gameStr[i + 2] == 'O')
			return true;
		if (gameStr[i] == 'O' && gameStr[i + 1] == 'O' && gameStr[i + 2] == 'M')
			return true;
	}
 
	// caso 3: columnas 1, 2, 3
	if (gameStr[2] == 'M' && gameStr[5] == 'O' && gameStr[8] == 'O') return true;
	for (int i = 0; i < 3; i++) {
		if (gameStr[i] == 'M' && gameStr[i + 3] == 'O' && gameStr[i + 6] == 'O')
			return true;
		if (gameStr[i] == 'O' && gameStr[i + 3] == 'O' && gameStr[i + 6] == 'M')
			return true;
	}
 
	return false;
}
 
int encodeString(string str) {
	int state = 0;
 
	for (int i = 0; i < 9; i++) {
		int num = 0;
 
		if (str[i] == 'O') {
			num = 1;
		} else if (str[i] == 'M') {
			num = 2;
		}
 
		state += (num * powThree[i]);
	}
 
	return state;
}
 
void dfs(int i, int j, string gameStr) {
	int state = encodeString(gameStr);
 
	if (visited[i][j][state]) return;
 
	visited[i][j][state] = true;
 
	Point p = grid[i][j];
 
	if (p.id != 'B' && p.id != '#' && p.id != '.') {
		if (gameStr[(p.y - 1) * 3 + (p.x - 1)] == ' ') {
			gameStr[(p.y - 1) * 3 + (p.x - 1)] = p.id;
		}
	}
 
	if (isWin(gameStr)) {
		res.insert(gameStr);
		return;
	}
 
	if (grid[i - 1][j].id != '#') dfs(i - 1, j, gameStr);
	if (grid[i][j - 1].id != '#') dfs(i, j - 1, gameStr);
	if (grid[i + 1][j].id != '#') dfs(i + 1, j, gameStr);
	if (grid[i][j + 1].id != '#') dfs(i, j + 1, gameStr);
};
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n;
	cin >> n;
	pair<int, int> bessie;
 
	for (int i = 0; i < n; i++) {
		for (int co = 0, j = 0; co < n * 3; co += 3, j++) {
			Point &p = grid[i][j];
 
			char a, b, c;
			cin >> a >> b >> c;
 
			p.id = a;
			p.x = -1;
			p.y = -1;
 
			if (a == 'M' || a == 'O') {
				p.x = b - '0';
				p.y = c - '0';
			} else if (a == 'B') {
				bessie = make_pair(i, j);
			}
		}
	}
 
	powThree[0] = 1;
	for (int i = 1; i < 9; i++) { powThree[i] = powThree[i - 1] * 3; }
 
	dfs(bessie.first, bessie.second, "         ");
 
	cout << res.size() << "\n";
}


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) {
		// caso 1: diagonal
		if (gameStr.charAt(0) == 'M' && gameStr.charAt(4) == 'O' &&
		    gameStr.charAt(8) == 'O')
			return true;
		if (gameStr.charAt(2) == 'M' && gameStr.charAt(4) == 'O' &&
		    gameStr.charAt(6) == 'O')
			return true;
 
		if (gameStr.charAt(0) == 'O' && gameStr.charAt(4) == 'O' &&
		    gameStr.charAt(8) == 'M')
			return true;
		if (gameStr.charAt(2) == 'O' && gameStr.charAt(4) == 'O' &&
		    gameStr.charAt(6) == 'M')
			return true;
 
		// caso 2: filas 1, 2, 3
		for (int i = 0; i < 9; i += 3) {
			if (gameStr.charAt(i) == 'M' && gameStr.charAt(i + 1) == 'O' &&
			    gameStr.charAt(i + 2) == 'O')
				return true;
			if (gameStr.charAt(i) == 'O' && gameStr.charAt(i + 1) == 'O' &&
			    gameStr.charAt(i + 2) == 'M')
				return true;
		}
 
		// caso 3: columnas 1, 2, 3
		for (int i = 0; i < 3; i++) {
			if (gameStr.charAt(i) == 'M' && gameStr.charAt(i + 3) == 'O' &&
			    gameStr.charAt(i + 6) == 'O')
				return true;
			if (gameStr.charAt(i) == 'O' && gameStr.charAt(i + 3) == 'O' &&
			    gameStr.charAt(i + 6) == 'M')
				return true;
		}
 
		return false;
	}
 
	static int encodeString(String str) {
		int state = 0;
 
		for (int i = 0; i < 9; i++) {
			int num = 0;
 
			char c = str.charAt(i);
			if (c == 'O') {
				num = 1;
			} else if (c == 'M') {
				num = 2;
			}
 
			state += (num * powThree[i]);
		}
 
		return state;
	}
 
	static void dfs(int i, int j, String gameStr) {
		int state = encodeString(gameStr);
 
		if (visited[i][j][state]) return;
 
		visited[i][j][state] = true;
 
		Point p = grid[i][j];
 
		if (p.id != 'B' && p.id != '#' && p.id != '.') {
			int idx = (p.y - 1) * 3 + (p.x - 1);
 
			if (gameStr.charAt(idx) == ' ') {
				StringBuilder sb = new StringBuilder(gameStr);
 
				sb.setCharAt(idx, p.id);
				gameStr = sb.toString();
			}
		}
 
		if (isWin(gameStr)) {
			results.add(gameStr);
			return;
		}
 
		if (grid[i - 1][j].id != '#') dfs(i - 1, j, gameStr);
		if (grid[i][j - 1].id != '#') dfs(i, j - 1, gameStr);
		if (grid[i + 1][j].id != '#') dfs(i + 1, j, gameStr);
		if (grid[i][j + 1].id != '#') dfs(i, j + 1, gameStr);
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
 
		int n = Integer.parseInt(br.readLine().trim());
		grid = new Point[n][n];
 
		int bessieX = -1, bessieY = -1;
 
		for (int i = 0; i < n; i++) {
			String line = br.readLine();
			for (int co = 0, j = 0; co < n * 3; co += 3, j++) {
				char a = line.charAt(co);
				char b = line.charAt(co + 1);
				char c = line.charAt(co + 2);
 
				Point p = new Point();
 
				p.id = a;
 
				if (a == 'M' || a == 'O') {
					p.x = b - '0';
					p.y = c - '0';
				} else if (a == 'B') {
					bessieY = i;
					bessieX = j;
				}
 
				grid[i][j] = p;
			}
		}
 
		powThree[0] = 1;
		for (int i = 1; i < 9; i++) { powThree[i] = powThree[i - 1] * 3; }
 
		dfs(bessieY, bessieX, "         ");
 
		out.println(results.size());
		out.flush();
	}
 
	private static class Point {
		char id;
		int x, y;
 
		Point() {
			this.id = ' ';
			this.x = -1;
			this.y = -1;
		}
	}
}


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):
		for j in range(3):
			cells[i][j] = b % 3
			b //= 3
 
	for r in range(3):
		if cells[r][0] == 2 and cells[r][1] == 1 and cells[r][2] == 1:
			return True
		if cells[r][0] == 1 and cells[r][1] == 1 and cells[r][2] == 2:
			return True
 
	for c in range(3):
		if cells[0][c] == 2 and cells[1][c] == 1 and cells[2][c] == 1:
			return True
		if cells[0][c] == 1 and cells[1][c] == 1 and cells[2][c] == 2:
			return True
 
	if cells[0][0] == 2 and cells[1][1] == 1 and cells[2][2] == 1:
		return True
	if cells[0][0] == 1 and cells[1][1] == 1 and cells[2][2] == 2:
		return True
	if cells[2][0] == 2 and cells[1][1] == 1 and cells[0][2] == 1:
		return True
	if cells[2][0] == 1 and cells[1][1] == 1 and cells[0][2] == 2:
		return True
 
	return False
 
 
def dfs(i, j, b):
	if visited[i][j][b]:
		return
 
	visited[i][j][b] = True
 
	a, x, y = grid[i][j]
 
	if a == "M" or a == "O":
		r, c = y - 1, x - 1
 
		idx = r * 3 + c
		current_char = (b // pow3[idx]) % 3
 
		if current_char == 0:
			new_char = 1 if a == "O" else 2
 
			b = (b % pow3[idx]) + new_char * pow3[idx] + (b - b % pow3[idx + 1])
 
			if not visited[i][j][b] and test_win(b):
				answers.add(b)
				return
 
			visited[i][j][b] = True
 
	if grid[i - 1][j][0] != "#":
		dfs(i - 1, j, b)
	if grid[i + 1][j][0] != "#":
		dfs(i + 1, j, b)
	if grid[i][j - 1][0] != "#":
		dfs(i, j - 1, b)
	if grid[i][j + 1][0] != "#":
		dfs(i, j + 1, b)
 
 
n = int(input())
grid = [[None] * n for _ in range(n)]
bessie = None
 
for i in range(n):
	line = input().strip()
	for j in range(n):
		a, b, c = line[j * 3], line[j * 3 + 1], line[j * 3 + 2]
		if a == "M" or a == "O":
			grid[i][j] = (a, int(b), int(c))
		else:
			grid[i][j] = (a, -1, -1)
			if a == "B":
				bessie = (i, j)
 
pow3 = [1] * 10
for i in range(1, 10):
	pow3[i] = pow3[i - 1] * 3
 
visited = [[[False] * 19683 for _ in range(n)] for _ in range(n)]
answers = set()
 
dfs(bessie[0], bessie[1], 0)
 
print(len(answers))