شکارچی گنج
Problem
واسیا یاب گنج با نقشه یک سیاه چال باستانی برخورد کرد. سیاه چال یک پیچ و خم اندازه NM (1NM100، NM100) است. هر سلول هزارتو یا خالی و قابل عبور است یا شامل یک دیوار است. شما فقط می توانید از یک سلول به یک سلول مجاور دیوار حرکت کنید (به عنوان مثال، هر سلول نمی تواند بیش از 4 سلول مجاور داشته باشد).
در یکی از سلول ها گنجی وجود دارد که واسیا می خواهد آن را بدست آورد. دخمه پرپیچ و خم دارای ورودی های K است که واسیا می تواند از آنجا سفر خود را آغاز کند.
باید مشخص شود که واسیا باید از کدام ورودی سفر خود را شروع کند تا مسافت طی شده تا گنج کمترین مقدار را داشته باشد. اگر چندین ورودی وجود دارد، ورودی را با کوچکترین عدد چاپ کنید.
ورودی
خط اول شامل 2 عدد N و M است که ابعاد ماز را مشخص می کند. شرح هزارتو به شرح زیر است: N خط با کاراکتر M. 0 به این معنی است که سلول آزاد است. 1 که یک دیوار در قفس وجود دارد. نماد * یک سلول با گنج را نشان می دهد (دقیقاً یکی از این سلول ها در هزارتو وجود دارد).
خط (N+2)امین عدد K (1<=K<= NxM) - تعداد ورودی‌های هزارتو است. بعد، خطوط K شامل مختصات ورودی ها هستند. بنابراین، خط i حاوی اعداد xi و yi است، به این معنی که ورودی i در خط xi و در ستون yi (1xiN1yiM) قرار دارد. تضمین می شود که مختصات ورودی ها به صورت زوجی متفاوت است و همه ورودی ها در سلول های خالی قرار دارند. هیچ یک از ورودی ها در قفس گنج نیست.
خروجی
لازم است یک عدد نمایش داده شود - عدد ورودی مورد نظر (شماره گذاری از 1 شروع می شود). اگر نمی توان به گنج دسترسی پیدا کرد، -1 را چاپ کنید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 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 |