Minimal Grid Path

Explicación

El problema pide el camino lexicográficamente más chico, lo que significa que queremos el string alfabéticamente más chico posible. Esto sugiere una estrategia voraz: en cada paso del camino, queremos elegir el carácter más chico disponible.

Sin embargo, una búsqueda voraz simple (elegir el único mejor vecino) falla porque varios caminos pueden ofrecer el mismo “mejor” carácter en el paso actual pero divergir después. Para resolverlo, no podemos restringirnos a un solo camino. En cambio, debemos seguir todos los caminos actualmente óptimos al mismo tiempo. Si varias celdas ofrecen el carácter mínimo ‘A’, las mantenemos todas como candidatas para el siguiente paso.

1. Entender la minimalidad lexicográfica

Un string $S$ es lexicográficamente menor que $T$ si, en la primera posición donde difieren, el carácter de $S$ es menor que el de $T$. Esto implica que los caracteres más tempranos del string tienen más peso. Nuestro objetivo es minimizar el 1er carácter, luego el 2do, y así sucesivamente. Esta estructura nos permite construir la solución carácter a carácter desde el inicio hasta el final.

2. Capas diagonales

En una grilla donde solo nos movemos Abajo o Derecha, cada celda $(r, c)$ es alcanzable en exactamente $r+c$ pasos. Esto significa que todos los candidatos para el $k$-ésimo carácter de nuestro camino están en la línea diagonal donde $r+c = k$.

Esta observación nos motiva a procesar la grilla diagonal por diagonal. Iterando $i$ de $0$ a $2n-2$, determinamos de forma sistemática el $i$-ésimo carácter del string final a partir de las mejores elecciones disponibles de la diagonal anterior.

3. El proceso de barrido

Usamos una tabla booleana 2D best_path para seguir qué celdas son parte de un prefijo válido y mínimo. Para cada diagonal $i$:

• Hallar el mejor carácter: recorremos todas las celdas válidas (donde best_path es verdadero) y miramos sus vecinos alcanzables (Abajo y Derecha). Hallamos el carácter mínimo global entre todos esos vecinos.
• Filtrar candidatos: una vez hallado el mejor carácter, actualizamos best_path para la siguiente diagonal. Una celda de la siguiente diagonal se marca como válida solo si contiene ese carácter mínimo y es alcanzable desde una celda válida actual.

Esto efectivamente “poda” los caminos subóptimos en cada capa, dejando solo las ramas que contribuyen al resultado lexicográficamente más chico.

Implementación

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

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n;
	cin >> n;
	vector<string> grid(n);
	for (auto &i : grid) cin >> i;
 
	// En una grilla n x n, cualquier camino de (0,0) a (n-1,n-1) tiene exactamente 2n-1 caracteres
	const int path_len = 2 * n - 1;
	string res;
	res += grid[0][0];
 
	// best_path[r][c] lleva la cuenta de qué celdas pueden
	// llevar al mejor resultado lexicográfico
	vector<vector<bool>> best_path(n, vector<bool>(n));
	best_path[0][0] = true;
 
	// Procesamos la grilla diagonal por diagonal
	for (int i = 0; i < path_len - 1; i++) {
		char best = 'z';  // Inicializar con el valor máximo posible
 
		// Pasada 1: mirar todos los vecinos de las celdas actualmente marcadas como "best" para
		// hallar el carácter más chico disponible para el siguiente paso.
		for (int r = 0; r <= min(n - 1, i); r++) {
			int c = i - r;
			if (c >= n || !best_path[r][c]) continue;
 
			if (r + 1 < n) best = min(best, grid[r + 1][c]);  // Abajo
			if (c + 1 < n) best = min(best, grid[r][c + 1]);  // Derecha
		}
 
		res += best;
 
		// Pasada 2: ahora que sabemos el mejor carácter, marcamos todas las celdas de la siguiente
		// diagonal (i + 1) que tienen este carácter y son alcanzables.
		for (int r = 0; r <= min(n - 1, i); r++) {
			int c = i - r;
			if (c >= n || !best_path[r][c]) continue;
 
			if (r + 1 < n && grid[r + 1][c] == best) { best_path[r + 1][c] = true; }
			if (c + 1 < n && grid[r][c + 1] == best) { best_path[r][c + 1] = true; }
		}
	}
 
	cout << res << '\n';
 
	return 0;
}