საჭადრაკო მხედარი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 128 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2009/10, NOV, BRONZE


მოცემულია მართკუთხა არე, რომელიც დაყოფილია X*Y კვადრატად
(1 <= X <= 150; 1 <= Y <= 150). თქვენ ამ არეზე ამოძრავებთ საჭადრაკო
მხედარს, რომელსაც არ შეუძლია დახტეს დაბრკოლებაზე, მაგრამ შეუძლია
გადაახტეს მას. არეზე მხედრის საწყისი პოზიცია აღნიშნულია '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
მხედარს შეუძლია საბოლოო პოზიციამდე 5 ნახტომში მივიდეს. 
ნახტომები ქვემოთ აღნიშნულია სიმბოლოებით A, B, C, ...
11 | . . . . . . . . . . 
10 | . . . . * . . . . .
9 | . . . . . . . . . .
8 | . . . * . * . . . .
7 | . . . . . . . * . .
6 | . . * . . * . . . F
5 | * . B . . . . . . .
4 | . . . * C . . * E .
3 | . A . . . . D . . .
2 | . . . * . . . . . *
1 | . . * . . . . * . .
0 ----------------------
0 1 2 3 4 5 6 7 8 9 10






მაგალითები

შესატანი მონაცემები
10 11 .......... ....*..... .......... ...*.*.... .......*.. ..*..*...H *......... ...*...*.. .K........ ...*.....* ..*....*.. დაკოპირება
გამოსატანი მონაცემები
5 დაკოპირება