Esquí a Campo Traviesa
El trayecto de esquí a campo traviesa en las Mulimpiadas de invierno está descrito como una cuadrícula de alturas x , cada elevación en el rango .
Algunas de las celdas en esta cuadrícula están designadas como puntos de camino para el trayecto. Los organizadores de las Mulimpiadas quieren asignar un rango de dificultad a todo el trayecto de tal manera que una vaca pueda llegar de cualquier punto de camino a otro punto de camino esquiando repetidamente de una celda a una celda adyacente entre celdas adyacentes con diferencia absoluta de altura de a lo más . Dos celdas son adyacentes si una está directamente al norte, sur, este u oeste de la otra. El rango de dificultad del trayecto es el mínimo tal que todos los puntos del camino son alcanzables mutuamente de esta manera.
Entrada
• Línea 1: Los enteros y .
• Líneas 2…1+M: Cada una de esas líneas contiene alturas enteras.
• Líneas 2+M…1+2M: Cada una de esas líneas contiene valores que son o o , con indicando que es un punto de camino.
Ejemplo de Entrada
3 5
20 21 18 99 5
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1
Detalles de la Entrada
El trayecto de esquí está descrito por una cuadrícula de alturas x . Las celdas superior-izquierda, superior-derecha e inferior-derecha están designadas como puntos de camino.
Salida
• Línea 1: El rango de dificultad para el trayecto (el valor mínimo de tal que todos los puntos de camino estén aún conectados desde cada otro).
Ejemplo de Salida
21
Detalles de la Salida
Si , todos los tres puntos de camino son alcanzables desde cada otro. Si , entonces el punto de camino superior-derecho no puede ser alcanzable desde los otros dos.
Comments