Cow Navigation

Explicación

En este problema, Bessie está en una grilla y quiere ir de la esquina inferior izquierda a la esquina superior derecha en la menor cantidad de movimientos posible. Una idea inicial podría ser modelar la grilla como un grafo, donde las celdas adyacentes están conectadas por aristas, y ejecutar un BFS para encontrar el camino más corto.

Sin embargo, dos restricciones adicionales juegan un papel en este problema: Bessie debe poder alcanzar el destino independientemente de la dirección en la que empiece, y solo puede moverse en la dirección a la que está mirando.

Imaginemos ahora que hay dos vacas paradas en la celda $(1, 1)$ , y ambas se mueven de la misma forma en cada operación. Como $N \leq 20$ , podemos modificar el grafo original para soportar este nuevo problema. Creemos un nuevo grafo $G'$ de la siguiente forma:

Para cada par de celdas en la grilla, $(x, y)$ y $(x_2, y_2)$ , agregamos $16$ nodos en el grafo almacenando seis parámetros cada uno:

coordenada $x$ de la vaca $a$
coordenada $y$ de la vaca $a$
coordenada $x$ de la vaca $b$
coordenada $y$ de la vaca $b$
dirección de la vaca $a$
dirección de la vaca $b$

para las $4 ^ 2$ direcciones a las que cada vaca podría estar mirando.

Dado este nuevo grafo, agregamos aristas entre dos “estados” que son alcanzables uno desde el otro. Por ejemplo, si aplicamos la operación “girar a la izquierda”, agregamos una arista al estado donde ambas direcciones de las vacas giran a la izquierda.

Sobre este nuevo grafo, podemos ejecutar un BFS directamente, y recuperar la respuesta en el estado $\{N, N, N, N, x, y\}$ donde $x$ e $y$ representan direcciones.

Implementación

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

C++


// created by Oleksandr Gorpynich
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int n;
struct state {
	int x1;
	int y1;
	int x2;
	int y2;
	int dir;
	int dist;
};
char arr[21][21];
int visited[21][21][21][21][4];
// x1, y1, x2, y2, dir
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
// arriba, izquierda, abajo, derecha
// probar si una celda es posible de visitar
bool inside(int x, int y) {
	if (x >= 0 && x < n && y >= 0 && y < n) {
		if (arr[x][y] != 'H') { return true; }
	}
	return false;
}
// marcar un estado como visitado
bool setvisited(state cur) { visited[cur.x1][cur.y1][cur.x2][cur.y2][cur.dir] = 1; }
// comprobar si un estado ya fue visitado
bool free(state cur) {
	if (visited[cur.x1][cur.y1][cur.x2][cur.y2][cur.dir] == -1) { return true; }
	return false;
}
int main() {
	ifstream in("cownav.in");
	ofstream out("cownav.out");
	in >> n;
	for (int x = 0; x < n; x++) {
		for (int y = 0; y < n; y++) { in >> arr[x][y]; }
	}
	memset(visited, -1, sizeof visited);
	queue<state> q;
	q.push({n - 1, 0, n - 1, 0});
	while (q.size() > 0) {
		state cur = q.front();
		q.pop();
		state ncur = cur;
		bool reachedend1 = false;
		bool reachedend2 = false;
		// comprobar si llegó al final
		if (cur.x1 == 0 && cur.y1 == n - 1) { reachedend1 = true; }
		if (cur.x2 == 0 && cur.y2 == n - 1) { reachedend2 = true; }
		if (reachedend1 && reachedend2) {
			out << ncur.dist << "\n";
			return 0;
		}
		// girar en sentido horario
		ncur = cur;
 
		ncur.dir = (cur.dir + 1) % 4;
		ncur.dist += 1;
		if (free(ncur)) {
			setvisited(ncur);
			q.push(ncur);
		}
		// girar en sentido antihorario
		ncur = cur;
		ncur.dir = (cur.dir - 1) == -1 ? 3 : (cur.dir - 1);
		ncur.dist += 1;
		if (free(ncur)) {
			setvisited(ncur);
			q.push(ncur);
		}
		// avanzar
		ncur = cur;
		if (inside(ncur.x1 + dx[ncur.dir], ncur.y1 + dy[ncur.dir]) && !reachedend1) {
			ncur.x1 += dx[ncur.dir];
			ncur.y1 += dy[ncur.dir];
		}
		if (inside(ncur.x2 + dx[(ncur.dir + 1) % 4],
		           ncur.y2 + dy[(ncur.dir + 1) % 4]) &&
		    !reachedend2) {
			ncur.x2 += dx[(ncur.dir + 1) % 4];
			ncur.y2 += dy[(ncur.dir + 1) % 4];
		}
		ncur.dist += 1;
		if (free(ncur)) {
			setvisited(ncur);
			q.push(ncur);
		}
	}
	out << -1 << "\n";
}