Esquí a Campo Traviesa


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Swift, VB

El trayecto de esquí a campo traviesa en las Mulimpiadas de invierno está descrito como una cuadrícula de alturas M x N (1 \leq M, N \leq 500), cada elevación en el rango 0... 1 000 000 000.

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 D 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 D. 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 D mínimo tal que todos los puntos del camino son alcanzables mutuamente de esta manera.

Entrada

• Línea 1: Los enteros M y N.

• Líneas 2…1+M: Cada una de esas M líneas contiene N alturas enteras.

• Líneas 2+M…1+2M: Cada una de esas líneas contiene N valores que son o 0 o 1, con 1 indicando que 1 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 3 x 5. 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 D tal que todos los puntos de camino estén aún conectados desde cada otro).

Ejemplo de Salida

21

Detalles de la Salida

Si D = 21, todos los tres puntos de camino son alcanzables desde cada otro. Si D < 21, entonces el punto de camino superior-derecho no puede ser alcanzable desde los otros dos.


Comments

There are no comments at the moment.