Problem
La cazadora de tesoros Vasya encontró un mapa de una antigua mazmorra. La mazmorra es un laberinto del tamaño de NM (1NM100, NM100). Cada celda del laberinto está vacía y se puede atravesar, o contiene una pared. Solo puede moverse de una celda a una celda adyacente a la pared (por ejemplo, cada celda no puede tener más de 4 celdas adyacentes).
En una de las celdas hay un tesoro que Vasya quiere conseguir. El laberinto tiene K entradas desde las cuales Vasya puede comenzar su viaje.
Se requiere determinar desde qué entrada Vasya necesita comenzar su viaje para que la distancia recorrida hasta el tesoro sea la menor. Si hay varias entradas de este tipo, imprima la entrada con el número más pequeño.
Entrada
La primera línea contiene 2 números N y M, que definen las dimensiones del laberinto. La descripción del laberinto sigue: N líneas con M caracteres cada una. 0 significa que la celda está libre; 1 que hay una pared en la jaula. El símbolo * denota una celda con un tesoro (hay exactamente una de esas celdas en el laberinto).
La línea (N+2) contiene el número K (1<=K<= NxM) -- el número de entradas al laberinto. A continuación, las líneas K contienen las coordenadas de las entradas. Por lo tanto, la i-ésima línea contiene los números xi y yi, lo que significa que la i-ésima entrada se encuentra en la xi-ésima línea y en la yi-ésima columna (1xiN1yiM). Se garantiza que las coordenadas de las entradas sean diferentes por pares y que todas las entradas estén ubicadas en celdas vacías. Ninguna de las entradas está en la jaula del tesoro.
Salida
Es necesario mostrar un número: el número de entrada deseado (la numeración comienza desde 1). Si no se puede alcanzar el tesoro, imprime -1.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
|
1 |
| 2 |
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
|
-1 |