Editorial for Laberinto

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: humbertoyusta

Subtarea 1:

Como $X = 0$ ~X = 0~. Podemos crear un grafo donde los nodos sean las posiciones $(a, b)$ ~(a, b)~ de la matriz, conectamos todos los $(a, b)$ ~(a, b)~ con $(a+1, b)$ ~(a+1, b)~ con costo 0, los $(a, b)$ ~(a, b)~ con los $(a-1, b)$ ~(a-1, b)~ con costo $0$ ~0~, y los $(a, b)$ ~(a, b)~ con los $(a, b+1)$ ~(a, b+1)~ con costo $1$ ~1~. Siempre que esas posiciones sean válidas ( $'.'$ ~'.'~). La solúcion del problema es la cantidad de nodos de ese grafo que tienen una distancia menor igual a $Y$ ~Y~ con respecto al nodo inicial $(r, c)$ ~(r, c)~. Se puede calcular con dijkstra en $O(nm\log{nm})$ ~O(nm\log{nm})~ o con 0-1 BFS en $O(nm)$ ~O(nm)~.

Para los que no lo conozcan el 0-1BFS es un algoritmo usado para buscar camino mínimo en un grafo en el que el peso de las aristas es 0 o 1. Es igual que el BFS común pero se hace con una doble cola(deque), y al updatear un nodo con una distancia mejor, se añande al principio de la cola si se llegó con costo 0, o al final si se llegó con costo 1. La complejidad es $O(V+E)$ ~O(V+E)~.

Subtarea 2:

Para esta subtarea modificaremos un poco los nodos, ahora los nodos son $(a, b, l)$ ~(a, b, l)~ que significa, en la posición $(a, b)$ ~(a, b)~ de la matriz habiendo hecho l movimientos hacia la izquierda, las aristas seran de los tipos siguientes:

Del nodo $(a, b, l)$ ~(a, b, l)~ al $(a+1, b, l)$ ~(a+1, b, l)~ o al $(a-1, b, l)$ ~(a-1, b, l)~ con costo $0$ ~0~.

Del nodo $(a, b, l)$ ~(a, b, l)~ al $(a, b-1, l+1)$ ~(a, b-1, l+1)~ con costo $0$ ~0~.

Del nodo $(a, b, l)$ ~(a, b, l)~ al $(a, b+1, l)$ ~(a, b+1, l)~ con costo $1$ ~1~.

La respuesta será la cantidad de posiciones $(a, b)$ ~(a, b)~ tal que hay algún nodo $(a, b, l)$ ~(a, b, l)~ para $0 \leq l \leq X$ ~0 \leq l \leq X~ que el costo de ir de $(r, c, 0)$ ~(r, c, 0)~ a él sea menor o igual a Y.

Con 0-1 BFS la complejidad es $O(nmX)$ ~O(nmX)~.

Subtarea 3:

Supongamos que comenzamos en la celda $(a, b)$ ~(a, b)~ y examinamos si podemos llegar a la celda $(c, d)$ ~(c, d)~.

Denotemos el número de movimientos realizados hacia la derecha como R y el número de movimientos hacia la izquierda como L

Claramente, $b + R - L = d$ ~b + R - L = d~

Es decir, $R - L = d - b = constante$ ~R - L = d - b = constante~, expresado de otra manera $R = L + const$ ~R = L + const~, donde $const$ ~const~ solo depende de la celda inicial y la celda objetivo.

Entonces solo necesitamos minimizar cualquiera de los movimientos hacia la izquierda o hacia la derecha, el otro también será óptimo.

Para calcular el número mínimo posible de movimientos $L$ ~L~ para llegar a alguna celda, podemos usar 0-1 bfs.

La solución es $O (nm)$ ~O (nm)~.

Comments

There are no comments at the moment.