Problem
Il cacciatore di tesori Vasya si è imbattuto in una mappa di un'antica prigione. Il dungeon è un labirinto di dimensioni NM (1NM100, NM100). Ogni cella del labirinto è vuota e attraversabile o contiene un muro. Puoi spostarti solo da una cella a una cella adiacente al muro (ad esempio, ogni cella non può avere più di 4 celle adiacenti).
In una delle celle c'è un tesoro che Vasya vuole prendere. Il labirinto ha K ingressi da cui Vasya può iniziare il suo viaggio.
È necessario determinare da quale ingresso Vasya ha bisogno di iniziare il suo viaggio in modo che la distanza percorsa fino al tesoro sia minima. Se sono presenti più input di questo tipo, stampa l'input con il numero più piccolo.
Input
La prima riga contiene 2 numeri N e M, che definiscono le dimensioni del labirinto. Segue la descrizione del labirinto: N righe con M caratteri ciascuna. 0 significa che la cella è libera; 1 che c'è un muro nella gabbia. Il simbolo * indica una cella con un tesoro (c'è esattamente una di queste celle nel labirinto).
La (N+2)esima riga contiene il numero K (1<=K<= NxM) -- il numero di ingressi al labirinto. Successivamente, le linee K contengono le coordinate degli input. Pertanto, la i-esima riga contiene i numeri xi e yi, il che significa che l'i-esimo input si trova nella xi-esima riga e nella yi-esima colonna (1xiN1yiM). È garantito che le coordinate degli input siano diverse a coppie e che tutti gli input si trovino in celle vuote. Nessuno degli ingressi è nella gabbia del tesoro.
Uscita
È necessario visualizzare un numero - il numero di input desiderato (la numerazione inizia da 1). Se il tesoro non può essere raggiunto, stampa -1.
Esempi
| # |
Input |
Uscita |
| 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 |