3691 - The Explorer Latin America - Mexico and Central America - 2006/2007
	PDF	PostScript	Submit	Ranking

THE EXPLORADOR

Un explorador debe decidir  una forma de construcción para  llegar de un punto A  a un punto  B. En orden para  ayudarse, el explorador ha hecho un mapa con los obstáculos que existen. Él dibujo en cuadrados  su mapa y  quiere un camino que pase por el menor número de cuadrados. El  sólo puede ir de un cuadrado al otro si  tienen un lado en común, es decir, no puede avanzar en  diagonal, y no puede pasar por un cuadrado que contiene un obstáculo .Cada cuadrado  del mapa es identificado por sus coordenadas, columna y filas. Las columnas  son numeradas de  izquierda a  derecha iniciándose con 0. Las filas son numeradas de arriba hacia abajo iniciándose en 0.

INPUT

Habrá múltiples entradas .La primera línea contiene el número  de entrada para evaluar. Cada entrada  será de la siguiente forma : primero, una  línea que contiene dos números enteros, N y M, separado por espacios, indicará el número de columnas y líneas, donde 1 <=N , M <=100 En cada uno después de líneas de M hay N numeradas , separado por espacios, que pueden ser 0 o 1,0 si no hay el obstáculo en el cuadrado correspondiente y 1 si lo hay. En la penúltima  línea la columna y la fila del punto A. En la última línea la columna y la fila de punto B. Todos  los casos de prueba tendrán al menos un modo de llegar A a B.

OUTPUT

El mínimo numero de cuadrados por el cual pasa entre a y b.

Sample Input

2 
3 3 
1 0 0 
1 0 0 
0 0 1
2 0 
0 2 
5 4 
0 1 0 0 0
0 0 1 1 0
0 1 0 0 0
0 0 0 0 0
1 3 
2 0

Sample Output

5 
9

---

Mexico and Central America 2006-2007

CARLOS EDUARDO CASTAÑEDA GALLARDO