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 קפיצות (ייתכנו אחרים באורך 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