Problem
Hazine avcısı Vasya eski bir zindanın haritasına rastladı. Zindan, NM boyutunda bir labirenttir (1NM100 , NM100). Labirentin her hücresi ya boş ve geçilebilir ya da bir duvar içerir. Yalnızca bir hücreden duvara bitişik bir hücreye geçebilirsiniz (örneğin, her hücrede en fazla 4 bitişik hücre olabilir).
Hücrelerden birinde Vasya'nın almak istediği bir hazine vardır. Labirentin, Vasya'nın yolculuğuna başlayabileceği K adet girişi vardır.
Hazineye kadar katedilen mesafenin en az olması için Vasya'nın yolculuğuna hangi girişten başlaması gerektiğinin belirlenmesi gerekmektedir. Bu tür birkaç giriş varsa, girişi en küçük sayıyla yazdırın.
Giriş
İlk satır, labirentin boyutlarını tanımlayan 2 sayı N ve M içerir. Labirentin açıklaması şu şekildedir: Her biri M karakterli N satır. 0, hücrenin boş olduğu anlamına gelir; 1 kafeste bir duvar olduğunu. * simgesi, hazinesi olan bir hücreyi belirtir (labirentte tam olarak böyle bir hücre vardır).
(N+2)inci satır, K sayısını (1<=K<= NxM) içerir -- labirent girişlerinin sayısı. Ardından, K satırları girişlerin koordinatlarını içerir. Böylece, i'nci satır xi ve yi sayılarını içerir, yani i'nci girdi xi'nci satırda ve yi'nci sütunda (1xiN1yiM) yer alır. Girişlerin koordinatlarının ikili olarak farklı olması ve tüm girişlerin boş hücrelerde yer alması garanti edilir. Girişlerin hiçbiri hazine kafesinde değil.
Çıktı
Bir sayının görüntülenmesi gereklidir - istenen giriş numarası (numaralandırma 1'den başlar). Hazineye ulaşılamıyorsa -1 yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 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 |