Swap Game

Pista

Consideremos todas las $9!$ configuraciones posibles del tablero como los nodos, y los movimientos como las aristas que los conectan. Hacemos BFS, partiendo de la configuración inicial dada.

La dificultad de este problema está en cómo implementamos el BFS. Presentamos dos soluciones: la primera es más rápida y la segunda es más fácil de escribir (ojo: la segunda puede dar TLE). La diferencia está en cómo se hashea la grilla.

Solución 1

Explicación

Como hay solo $9!$ estados posibles de la grilla, podemos usar BFS para hallar la cantidad de movimientos necesarios para llegar al $\texttt{target}$ desde la grilla inicial. Representamos cada grilla como un número en base $9$ .

Para cada grilla, podemos intercambiar dos casillas adyacentes horizontalmente o dos adyacentes verticalmente. Si todavía no procesamos esta grilla nueva, empujamos la grilla nueva y la distancia a la cola y la marcamos como visitada en el arreglo $\texttt{vis}$ . Cuando llegamos a la grilla ordenada, imprimimos $\texttt{dist}$ .

Implementación

Complejidad temporal: $\mathcal{O}(N^2!)$ , donde $N$ es el lado de la grilla

C++


#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
int powers[10];
 
// intercambia dos piezas y devuelve la grilla nueva
int move(int grid, int i, int j) {
	int a = grid % powers[i + 1] / powers[i];
	int b = grid % powers[j + 1] / powers[j];
	return grid - a * powers[i] - b * powers[j] + b * powers[i] + a * powers[j];
}
 
int main() {
	powers[0] = 1;
	for (int i = 1; i < 10; i++) { powers[i] = 9 * powers[i - 1]; }
	vector<bool> vis(powers[9], false);
	// la grilla final a la que queremos llegar
	int target = 0;
	for (int i = 8; i >= 0; i--) { target += (8 - i) * powers[i]; }
	int grid = 0, num;
	for (int i = 8; i >= 0; i--) {
		cin >> num;
		grid += (num - 1) * powers[i];
	}
	queue<pair<int, int>> q;
	q.push({grid, 0});
	while (!q.empty()) {
		auto [g, dist] = q.front();
		q.pop();
		// si llegamos al target, podemos imprimir la cantidad de movimientos
		if (g == target) {
			cout << dist << endl;
			return 0;
		}
		// intercambiar dos piezas adyacentes horizontalmente
		for (int i = 0; i < 8; i++) {
			if (i % 3 == 2) { continue; }
			int swapped = move(g, 8 - i, 8 - (i + 1));
			if (!vis[swapped]) {
				q.push({swapped, dist + 1});
				vis[swapped] = true;
			}
		}
		// intercambiar dos piezas adyacentes verticalmente
		for (int i = 0; i < 6; i++) {
			int swapped = move(g, 8 - i, 8 - (i + 3));
			if (!vis[swapped]) {
				q.push({swapped, dist + 1});
				vis[swapped] = true;
			}
		}
	}
	return 0;
}

Solución 2

Explicación

Por ejemplo, la grilla del caso de prueba,


2 1 3
7 5 9
8 4 6

se convierte en “213759846”.

Luego hacemos BFS de forma normal, pero con algunos cambios importantes.

Como no podemos usar strings como índices de un arreglo, guardamos la “profundidad” de cada string (cantidad de movimientos necesarios para alcanzar una configuración del tablero) dentro de la cola.
También guardamos los strings (configuraciones del tablero) ya vistos en un unordered_set, porque usar conjuntos (sets) normales (ordenados) sería demasiado lento.

Implementación

Complejidad temporal: $\mathcal{O}(N^2!)$ , donde $N$ es el lado de la grilla

C++


#include <bits/stdc++.h>
using namespace std;
 
unordered_set<string> visited;
 
// Definido globalmente para usarlo en process_swap
queue<pair<string, int>> q;
int moves;
string curboard;
 
// Procesa el intercambio de los números en las posiciones x, y
void process_swap(int x, int y) {
	swap(curboard[x], curboard[y]);
	// Verificar si ya visitamos este tablero potencial
	if (visited.find(curboard) == visited.end()) {
		q.push({curboard, moves + 1});
		visited.insert(curboard);
	}
	// Restaurar el tablero original
	swap(curboard[x], curboard[y]);
}
 
int main() {
	string inp;
	// Reescribir la entrada como un string
	for (int i = 0; i < 9; i++) {
		int a;
		cin >> a;
		inp += to_string(a - 1);
	}
 
	q.push({inp, 0});
	while (!q.empty()) {
		tie(curboard, moves) = q.front();
		q.pop();
		if (curboard == "012345678") {
			cout << moves << endl;
			return 0;
		}
 
		// Intercambios horizontales
		for (int i = 0; i < 9; i += 3) {
			process_swap(i, i + 1);
			process_swap(i + 1, i + 2);
		}
		// Intercambios verticales
		for (int i = 0; i < 3; i++) {
			process_swap(i, i + 3);
			process_swap(i + 3, i + 6);
		}
	}
}