Dəli Kral

Kral Peter A krallığında yaşayır, qızı isə B krallığında. Kral bir məktub aldı ki, qızı bir uşaq dünyaya gətirib. Kral nəvəsini görmək üçün çox səbirsizdir! Təəssüf ki, bu asan olmayacaq.

A və B krallıqları bir meşə ilə ayrılır. Meşədə çoxlu düşmənlər var və Kral onlarla qarşılaşmaq istəmir. Əgər onlar kralı B krallığına gedərkən hücum etsələr, o, bir daha nəvəsini və qızını görə bilməyəcək, çünki bu ölümcül nəticələrə səbəb ola bilər.

Kralın Gizli Şurası düşmənlərin yerləşdiyi yerlər haqqında məlumata malikdir, bu da kral üçün işləri asanlaşdırır. Naməlum səbəbdən meşə M×N ölçülü bir şahmat taxtasıdır. (M - sıra sayı, N - sütun sayı). N, M ≤ 100 müsbət tam ədədlərdir.

Kralın düşmənləri şəkildə göstərildiyi kimi atlarla hərəkət edə bilərlər. Adətən atlar şahmatda belə hərəkət edir (və ya sıçrayır). Təəssüf ki, kral A nöqtəsindən B nöqtəsinə təyyarə ilə gedə bilmir, çünki hələ icad edilməyib. Beləliklə, o, şahmat kralı kimi hərəkət edir (ətraflı məlumat üçün şəkilə baxın).

Kral düşmənin atı X kvadratında olduqda o kvadrata keçə bilmir. Kral hərəkət edərkən atlar hərəkət etmir, lakin əgər ən azı bir at bir hərəkətlə X kvadratına çata bilirsə, kral o kvadrata keçə bilmir (istisna hallarda X kvadratı ya A krallığı, ya da B krallığıdır).

Siz A krallığının Elektron Kəşfiyyat şöbəsinin rəisisiniz (bu arada, kompüterlər artıq icad edilib). Sizdən kralın nəvəsini görmək üçün çox narahat olduğu üçün A krallığından B krallığına ən qısa marşrutun uzunluğunu tapmağınız xahiş olunur.