teddy online judge

29. Reparaciones

Limite de tiempo : 1 seg.   Total runs : 90  Aceptados : 29

El centro de la ciudad de Puebla, en México, es un lugar muy sencillo de ubicarte. Contando únicamente con el nombre de la calle, puedes saber qué sentido tiene la calle, y qué tan lejos estás de tu destino. Esto es gracias a que las calles del centro forman una cuadrícula, y las calles están nombradas con números y el sentido del tráfico. Así, podemos encontrar nombres como Calle 6 Oriente.

Tu amigo José se va a mudar al centro de Puebla para trabajar en Innovación Tecnológica y Computación (ITC), y est´ encantado con la idea de los nombres de las calles. Como lleva apenas dos semanas trabajando, aún no tiene recursos para comprar un automóvil, así que se desplaza a pie. El problema es que, debido a las recientes lluvias, algunos segmentos de calles tuvieron que ser cerrados por reparación. Afortunadamente, el ayuntamiento de Puebla publicó mapas con las calles cerradas por reparación.

José quiere saber cuánto tíempo le tomaría llegar desde su casa a su trabajo, buscando obviamente que utilice la ruta más corta para ello (tiende a llegar tarde a veces, y su jefe amenazó con despedirlo si volvía a llegar tarde). Asumiremos que José camina a 50 m/minuto y cada cuadra mide 50 metros.

Entrada

La entrada consiste en un número entero k (1 <= 20 <= k) que nos indican el número de casos de prueba. La primera línea de cada caso de prueba consta de seis números enteros, separados por un espacio. El primer par de enteros nos indica las coordenadas x, y de la casa de tu amigo José, el segundo par de enteros las coordenadas de su trabajo, y el tercer par nos indican las dimensiones (ancho y alto, 1 <= ancho,alto <= 100) del mapa proporcionado por el municipio de Puebla. Las siguientes alto líneas tienen ancho dígitos. Cada dígito representa una cuadra de la ciudad. Si el dígito es 1, la calle está siendo reparada. Si el dígito es 0, la calle está disponible para caminar sobre ella. La esquina superior izquierda se designa como el origen, y tiene coordenadas (0, 0). Asume que siempre existe por lo menos un camino para llegar, y que tanto la casa como el trabajo de José están en calles que no están siendo reparadas.

Salida

Para caso de prueba, debes desplegar la frase "Caso k: m minutos." donde m es el tiempo en minutos que José debe caminar para llegar de su casa al trabajo y k corresponde el número de caso de prueba (están numerados secuencialmente, empezando por 1).

Entrada de prueba

1
0 0 3 4 4 5
0100
0000
1000
0110
0000

Salida de prueba

Caso 1: 8 minutos.