Qısqanc kraliça#2487
Şahzadə və Şah N \times N ölçülü şahmat taxtasında yerləşirlər, burada bəzi xanalar kəsilib. Hər fiqur digərini tutmaq istəyir. Hər iki tərəf optimal oynadığı halda, bir tərəfin qalib gəlməsi üçün lazım olan minimal gediş sayını müəyyən edin. Qalib vəziyyət odur ki, uduzan tərəf tutulmadan qaça bilməsin (nümunələrə baxın).
Kəsilmiş xanalar üzərinə çıxmaq, onların üzərindən tullanmaq və ya o xanaların üzərindən tutmaq qadağandır.
Əgər bir fiqur tələyə düşərsə, o, təhlükəsiz sayılır və oyun heç-heçə ilə başa çatır.
Zəmanət verilir ki, Şahzadə və Şah fərqli xanalar üzərində yerləşiblər və gediş sırası olan tərəf dərhal digərini tuta bilmir.
İlk sətirdə iki tam ədəd və (2 \leq N \leq 12, 0 \leq M \leq 142) verilir, burada kəsilmiş xanaların sayıdır. Sonrakı sətirin hər birində kəsilmiş xanaların koordinatları göstərilir. Sonuncu sətirdə isə Şahzadənin və Şahın koordinatları və növbənin kimdə olduğu verilir (Q — Şahzadənin, K — Şahın növbəsi).
Aşağıdakı mesajlardan birini çap edin:
Queen wins in moves.,
King wins in moves.,
və ya The game will end in a draw.
Burada müvafiq tərəfin qalib gəlməsi üçün lazım olan ümumi gediş sayıdır.
Nümunə 1