	4128 - Steam Roller World Finals - Banff Springs, Alberta - 2007/2008
	PDF	PostScript	Submit		Ranking

Johnny conduce un rodillo de vapor, que al igual que todos los rodillos de vapor es lento y toma un tiempo relativamente largo para empezarse a mover, cambiar de dirección, frenar y detenerse por completo. Johnny acaba de terminar su jornada de trabajo y su conduce a casa en su rodillo de vapor para ver a su esposa. Su tarea es encontrar el camino más rápido para él y su rodillo de vapor.

La ciudad donde vive Johnny tiene una estructura regular (la calle forma un sistema ortogonal). Las calles de la ciudad se establecen en una cuadrícula rectangular de intersecciones. Cada intersección está conectada a sus vecinos (hasta cuatro de ellos) por una calle. Cada calle está exactamente a una cuadra de largo. Cuando Johnny entra en una calle, que siempre debe viajar hasta el otro extremo (continúe a la siguiente intersección). A partir de ese momento, él puede continuar en ninguna de las cuatro posibles direcciones a otra intersección, y así sucesivamente.

Al estudiar las condiciones de las carreteras de las calles, Johnny ha calculado el tiempo necesario para ir de un extremo a otro de todas las calles de la ciudad. El tiempo es el mismo para ambas direcciones. Sin embargo, los cálculos de Johnny sólo están en virtud de la condición ideal para que el rodillo de vapor ya este en marcha cuando se entra en una calle y no tiene necesidad de acelerar o frenar. Cada vez que el rodillo de vapor cambia de dirección en una intersección directamente antes o después de una calle, la estimación de tiempo ideal para cada calle debe ser duplicada. Lo mismo si el rodillo empieza por un movimiento de un punto (por ejemplo, en el inicio de viaje de Johnny) o llega a un punto (por ejemplo, al final de su viaje).

La siguiente imagen muestra un ejemplo. Los números muestran el `` ideal "tantas veces cuanto sea necesario para conducir a través de las correspondientes calles. Calles con los números que faltan no se pueden utilizar para los rodillos de vapor. Johnny quiere ir de la esquina superior izquierda de la parte inferior derecha.

$\epsfbox{p4128.eps}$

El camino que consta de calles con la etiqueta 9 parece ser más rápido en la primera vista. Sin embargo, debido a los dispositivos de frenado y la aceleración de las restricciones, se tarda el doble del tiempo estimado para cada calle en el camino, haciendo que el tiempo total de 108. El camino a lo largo de las calles etiquetados con 10's es más rápido porque Johnny puede conducir a dos de las calles a la plena velocidad, dando un tiempo total de 100.

ENTRADA

La entrada consiste de varios casos de prueba. Cada caso de prueba se inicia con seis números positivos: R, C, r₁, c₁, r₂, y c₂. R y C, describir el tamaño de la ciudad, r1, c1 son las coordenadas de inicio, y r₂, c₂ son las coordenadas de la casa de Johnny. Las coordenadas de inicio son diferentes de las coordenadas de la casa de Johnny. El número de cumplir las siguientes condiciones: 1 $\le$ r₁, r₂ $\le$ R $\le$ 100, 1 $\le$ c₁, c₂ $\le$ C $\le$ 100.

Después de los seis números, hay C - 1 no negativos que describe el tiempo necesario para conducir en las calles entre las intersecciones (1,1) y (1,2), (1,2) y (1,3), (1, 3) y (1,4), y así sucesivamente. Luego hay C no negativos que describe el tiempo necesario para conducir en las calles entre las intersecciones (1,1) y (2,1), (1,2) y (2,2), y así sucesivamente. Después de eso, otro C - 1 no negativos describir la siguiente fila de las calles en todo el ancho de la ciudad. La entrada continúa de esta manera para describir todas las calles de la ciudad. Cada entero especifica el tiempo necesario para conducir a través de la correspondiente calle (no superior a 10000), siempre que el rodillo de vapor a través de productos directamente sin iniciar, parar o girar en ambos extremos de la calle. Si cualquier combinación de uno o más de estos eventos ocurre, el tiempo se multiplica por dos. Cualquiera de estos enteros puede ser cero, en cuyo caso la correspondiente calle no se puede utilizar en absoluto.

El último caso de prueba es seguido de seis ceros.

Todos los números están separados por lo menos con un blanco (espacio, ficha, o nueva línea), pero cualquier cantidad adicional de espacio en blanco (incluyendo líneas vacías) puede estar presente para mejorar la legibilidad.

SALIDA

Para cada caso de prueba, imprimir el número de caso (comenzando por el 1) seguido por el mínimo tiempo necesario para ir de intersección x₁, y₁ a x₂, y₂. Si el viaje no se puede lograr (inutilizable debido a las calles), imprimir la palabra "imposible" en su lugar.

MUESTRA DE ENTRADA

4 4 1 1 4 4

10 10 10

9 0 0 10

0 0 0

9 0 0 10

9 0 0

0 9 0 10

0 9 9

2 2 1 1 2 2 0 1 1 0

0 0 0 0 0 0

MUESTRA DE SALIDA

Case 1: 100

Case 2: Impossible

Banff Springs, Alberta 2007-2008

Tests-Setter: Derek Kisman

Traducido por: David Jacinto Sandoval