Skip to Content
CTRL K

What's Up With Gravity

Análisis oficial (C++) 

Explicación

Como este problema se puede reducir a un problema de camino más corto con longitudes de arista 00 o 11, podemos usar BFS. Una arista de transición tiene peso 11 si la gravedad se invierte o 00 si el Capitán Bovidian solo se mueve a la izquierda o a la derecha. Primero agregamos todos los bloques alcanzables hacia la izquierda y hacia la derecha a la cola. Cada elemento de la cola es una 4-tupla que contiene la fila y la columna del bloque, la cantidad de inversiones necesarias para llegar a él, y la dirección de la gravedad. Luego, para cada bloque de la cola, cambiamos la gravedad y hacemos otra búsqueda hacia la izquierda y la derecha, agregando eventualmente nuevos bloques al final de la cola. De esta forma, siempre revisaremos primero los bloques que requieren menos inversiones antes de avanzar.

Durante el proceso de búsqueda, almacenamos la cantidad de inversiones necesarias para llegar a un cierto bloque. Solo visitamos bloques que aún no fueron visitados.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
/**
 * Con la dirección de gravedad dada, calcular la fila en la que el capitán
 * caerá.
 * @param direc Dirección de la gravedad, 1 o -1
 */
int fall_to_row(int r, int c, int direc, const vector<vector<char>> &grid) {
	while (grid[r][c] == '.' || grid[r][c] == 'C' || grid[r][c] == 'D') {
		if (grid[r][c] == 'D') { return r; }
		if (grid[r + direc][c] == '#') { return r; }
		r += direc;
	}
	return -1;
}
 
/**
 * Encontrar todos los bloques alcanzables desde [r, c] yendo a izquierda y
 * derecha, sin invertir la gravedad.
 * @param flips Cantidad de inversiones ya realizadas para llegar a [r, c]
 * @param direc Dirección actual de la gravedad, 1 o -1
 */
void search_horizontally(int r, int c, int flips, int direc, queue<array<int, 4>> &bfs,
                         vector<vector<int>> &flip_count,
                         const vector<vector<char>> &grid) {
	// si está fuera de los límites o ya fue visitado, no seguir
	if (r <= 0 || grid[r][c] == '-' || flip_count[r][c] >= 0) { return; }
	flip_count[r][c] = flips;
	bfs.push({r, c, flips, direc});
 
	search_horizontally(fall_to_row(r, c + 1, direc, grid), c + 1, flips, direc, bfs,
	                    flip_count, grid);
	search_horizontally(fall_to_row(r, c - 1, direc, grid), c - 1, flips, direc, bfs,
	                    flip_count, grid);
}
 
int main() {
	freopen("gravity.in", "r", stdin);
	freopen("gravity.out", "w", stdout);
 
	int N, M;
	cin >> N >> M;
 
	pair<int, int> start, destination;
 
	// el borde se marca como '-'
	vector<vector<char>> grid(N + 2, vector<char>(M + 2, '-'));
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == 'C') {
				start = {i, j};
			} else if (grid[i][j] == 'D') {
				destination = {i, j};
			}
		}
	}
 
	/*
	 * flip_count[r][c] := cuántas inversiones se necesitan para alcanzar el
	 * bloque en la fila r-ésima y la columna c-ésima
	 */
	vector<vector<int>> flip_count(N + 2, vector<int>(M + 2, -1));
	// {fila, columna, cantidad de inversiones, dirección de la gravedad}
	queue<array<int, 4>> bfs;
	// dejar que el capitán caiga y hacer una búsqueda a izquierda y derecha
	search_horizontally(fall_to_row(start.first, start.second, 1, grid), start.second,
	                    0, 1, bfs, flip_count, grid);
 
	while (!bfs.empty()) {
		int r, c, flips, direc;
		r = bfs.front()[0];
		c = bfs.front()[1];
		flips = bfs.front()[2];
		direc = bfs.front()[3];
		bfs.pop();
 
		// invertir la gravedad
		r = fall_to_row(r, c, -direc, grid);
		// buscar a izquierda y derecha y agregar nuevos bloques a la cola
		search_horizontally(r, c, flips + 1, -direc, bfs, flip_count, grid);
	}
 
	cout << flip_count[destination.first][destination.second] << endl;
}
Fundamentos