← Volver a los ejercicios

Enchanted Forest: el peligro se calcula, no se lee

La amplitud es la misma del laberinto. Lo que cambia está antes: las celdas prohibidas no vienen en la entrada, salen de la distancia a cada Jigglypuff. Aquí hay que marcarlas a mano y comprobarlas antes de que el recorrido arranque.

1. El bosque y la predicción

Entrada: un bosque de R × C intersecciones, numeradas desde (1,1); m posiciones bloqueadas; n Jigglypuffs, cada uno en (x, y) con volumen L. Una posición es peligrosa si está a distancia euclidiana L o menos de algún Jigglypuff.  Salida: el mínimo de pasos de (1,1) a (R,C) sin pisar bloqueadas ni peligrosas, o Impossible.

Bosque:

¿Cuántos pasos hay hasta la salida? (−1 si es imposible)

2. Marque el peligro

Haga clic en cada celda que quede a distancia L o menos de un Jigglypuff. Las rocas y los Jigglypuffs ya están puestos; E es la entrada y S la salida. Las filas y las columnas van numeradas como en el enunciado.

libre bloqueada Jigglypuff peligrosa
Al comprobar, una celda que falta queda con borde ámbar y un signo de pregunta; una que sobra, con borde rojo.

3. Ejecute y mire las capas

Azul oscuro: la celda que salió de la cola. Borde ámbar: la celda que se está mirando. Cada celda alcanzada muestra su distancia.

Cola: vacía
Paso 0 de 0
La línea 15 pregunta por mundo[nr][nc]: ahí es donde entra lo que usted marcó arriba. La amplitud no distingue una roca de una celda peligrosa; para ella las dos valen −1.

4. Una fila por celda que sale de la cola

TurnoSaleSu distanciaEncola

5. Qué cae dentro del volumen

Un Jigglypuff con L = 1. Sin rocas alrededor, ¿qué celdas quedan peligrosas?

6. Cuando la entrada es peligrosa

Si (1,1) queda dentro del volumen de un Jigglypuff, ¿qué hace salida_mas_corta?
La pregunta de la línea 3 es la que cubre el caso: si la entrada es −1 no hay nada que encolar, y la matriz de distancias ya trae la respuesta. El programa imprime Impossible. sin un if aparte para la entrada.

7. Para llevarse

Sin solución aquí. marcar_peligro revisa solo el cuadrado de lado 2L + 1 centrado en cada Jigglypuff, en vez de recorrer el bosque entero. Con R = C = 200 y un Jigglypuff de L = 3, ¿cuántas celdas revisa de una forma y de la otra? ¿Y con los n = 100 Jigglypuffs que admite el enunciado? Escriba el costo de armar el mundo en términos de R, C, n y L, y diga a partir de qué L deja de valer la pena el recorte.