مطلوب تحديد المدخل الذي يحتاج منه فاسيا لبدء رحلته بحيث تكون المسافة المقطوعة إلى الكنز هي الأقل. إذا كان هناك العديد من هذه المدخلات ، فقم بطباعة الإدخال باستخدام أصغر رقم.
يحتوي السطر الأول على رقمين N و M يحددان أبعاد المتاهة. فيما يلي وصف المتاهة: N سطور كل منها حرف M. 0 يعني أن الخلية مجانية ؛ 1 ـ أن يوجد جدار في القفص. يشير الرمز * إلى خلية بها كنز (توجد خلية واحدة بالضبط في المتاهة).
& nbsp؛
يحتوي السطر (N + 2) th على الرقم K (1 & lt؛ = K & lt؛ = NxM) - عدد مداخل المتاهة. بعد ذلك ، تحتوي خطوط K على إحداثيات المدخلات. وبالتالي ، يحتوي السطر الأول على الأرقام xi و yi ، مما يعني أن المدخلات i تقع في السطر xi-th وفي العمود yi-th (1xiN1yiM). من المضمون أن تكون إحداثيات المدخلات مختلفة بشكل زوجي ، وأن جميع المدخلات موجودة في خلايا فارغة. لا يوجد أي من المداخل في قفص الكنز.
& nbsp؛
الإخراج
من الضروري عرض رقم واحد - رقم الإدخال المطلوب (يبدأ الترقيم من 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 |