Queen#618
Ümumi bir şahmat taxtasında (mütləq 8 \times 8 deyil) bir vəzir yerləşdirilib. Onun hazırda olduğu xanayı və çatmalı olduğu xanayı bilirsiniz. Problem ondadır ki, bəzi xanalarda düşmənin fiqurları var. Lakin bu fiqurlar dərin yuxudadırlar, buna görə vəzir səssizcə istədiyi qədər hərəkət edə bilər. Vəzir bu düşmən fiqurlarının üzərindən keçə və ya onları vura bilmir, çünki bu halda onları oyadacaq.
Sizdən tələb olunan, vəzirin hədəf xanaya çatmaq üçün etməli olduğu minimal hərəkət sayını müəyyən edən proqram yazmaqdır.
Proqram əsas tərtibatdan şahmat taxtasının ölçülərini oxuyur: əvvəlcə şaquli (2 \leq w \leq 26), sonra üfüqi (2 \leq h \leq 99) xətlərin sayını. Sonra isə başlanğıc və son hədəf xananın koordinatları, sonra isə düşmən fiqurlarının sayı (0 \leq K \leq w \cdot h - 2) verilir. Bundan sonra cüt ədəd — hər bir düşmən fiqurunun koordinatları yazılır. Bütün ədədlər boşluqla ayrılıb. Bütün koordinatlar müsbət təbii ədədlərdir və uyğun olaraq və -dən çox böyük deyil. Əvvəlcə şaquli, sonra isə üfüqi koordinat verilir. Başlanğıc və son xanalarda düşmən fiqurları yoxdur və heç iki düşmən fiquru eyni xanada yerləşmir.
Proqram bir tam ədəd çıxış verir: vəzirin başlanğıc xanadan hədəf xanaya çatması üçün lazım olan minimal hərəkət sayı və ya əgər çatmaq mümkün deyilsə, çıxarılır.
Nümunə 1