بادل Farmer John إحدى أبقاره بأخرى يسميها Farmer Don «The Knight». تقفز كحصان الشطرنج: خانتين جانبًا وواحدة لأعلى، أو خانتين لأسفل وواحدة جانبًا، إلخ. لا تهبط على صخور أو أشجار، لكنها تجوب المرعى المقسم إلى $X$ في $Y$ خانة ($1 \le X \le 150$؛ $1 \le Y \le 150$).

تحب «The Knight» التبن أيضًا. بخريطة البداية والشجر والشجيرات والصخور وبقية العقبات ورزمة التبن، حدد عدد القفزات للوصول. K البقرة و* عقبة وH التبن. خريطة نموذجية:

                    11 | . . . . . . . . . .
                    10 | . . . . * . . . . . 
                     9 | . . . . . . . . . . 
                     8 | . . . * . * . . . . 
                     7 | . . . . . . . * . . 
                     6 | . . * . . * . . . H 
                     5 | * . . . . . . . . . 
                     4 | . . . * . . . * . . 
                     3 | . K . . . . . . . . 
                     2 | . . . * . . . . . * 
                     1 | . . * . . . . * . . 
                     0 ----------------------
                                           1 
                       0 1 2 3 4 5 6 7 8 9 0

المسار A وB وC وهكذا يصل بخمس قفزات (قد توجد مسارات أخرى بطول 5):

                    11 | . . . . . . . . . .
                    10 | . . . . * . . . . .
                     9 | . . . . . . . . . .
                     8 | . . . * . * . . . .
                     7 | . . . . . . . * . .
                     6 | . . * . . * . . . F<
                     5 | * . B . . . . . . .
                     4 | . . . * C . . * E .
                     3 | .>A . . . . D . . .
                     2 | . . . * . . . . . *
                     1 | . . * . . . . * . .
                     0 ----------------------
                                           1
                       0 1 2 3 4 5 6 7 8 9 0

تلميح: ربما الأسهل طابور بسيط أول داخل أول خارج، ينفذ بعدة مصفوفات متوازية.

الإدخال

• السطر 1: الصحيحان $X$ و$Y$ تفصلهما مسافة.
• الأسطر $2..Y+1$: السطر $Y-i+2$ يحتوي $X$ محارف بلا مسافات للصف $i$ من الخريطة (تقرأ بترتيب الرسم أعلاه).

الإخراج

• السطر 1: صحيح، أقل عدد قفزات للتبن. الوصول ممكن دائمًا.

أمثلة

الإدخال 1

10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..

الإخراج 1

5

مؤلف المسألة: Rob Kolstad، 2009