Charcos de Lodo.
El Granjero Juan ha salido de su casa temprano a las 6 AM para el ordeño diario de Bessie. Sin embargo, en la tarde anterior el vio una fuerte lluvia, y los campos están algo enlodados. GJ comienza en el punto en el plano de coordenadas y se dirige hacia Bessie quien está ubicada en el punto . El puede ver charcos de lodo, ubicados en los puntos del campo. Cada charco ocupa solo el punto en el que está. Habiendo comprado recientemente botas nuevas, el Granjero Juan no quiere absolutamente ensuciarlas parándose sobre lodo, pero quiere llegar a donde Bessie tan rápido como sea posible. A él ya se le hizo tarde debido a que él tuvo que contar todos los charcos. Si el Granjero Juan puede viajar únicamente paralelo a los ejes y girar en puntos con coordenadas enteras, ¿cuál es la distancia más corta que él debe viajar para llegar a donde Bessie y mantener limpias sus botas? Siempre existirá un camino sin lodo que el Granjero Juan pueda tomar para llegar a donde Bessie.
Entrada
• Línea 1: Tres enteros separados por espacio: y .
• Líneas 2… N+1: la línea contiene dos enteros separados por espacio.
Ejemplo de Entrada
1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2
Detalles de la Entrada
Bessie está en el punto . El Granjero Juan ve 7 charcos de lodo; ubicados en los puntos: . Gráficamente:
4 . . . . . . . .
3 . M . . . . . .
Y 2 . . M B M . M .
1 . M . M . M . .
0 . . * . . . . .
-1 . . . . . . . .
-2-1 0 1 2 3 4 5
X
Salida
• Línea 1: La distancia mínima que el Granjero Juan debe viajar para llegar a donde está Bessie sin parase en el lodo.
Ejemplo de Salida
11
Detalles de la Salida
El mejor camino para el Granjero Juan es y , llegando finalmente a donde Bessie:
4 ******* . . . .
3 * M . * . . . .
Y 2 * . M B M . M .
1 * M . M . M . .
0 ***** . . . . .
-1 . . . . . . . .
-2-1 0 1 2 3 4 5
X
Comments