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.
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.
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.
Azul oscuro: la celda que salió de la cola. Borde ámbar: la celda que se está mirando. Cada celda alcanzada muestra su distancia.
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.| Turno | Sale | Su distancia | Encola |
|---|
salida_mas_corta?Impossible. sin un if aparte para la
entrada.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.