یک جدول $n \times m$ داریم که بعضی از خانه‌های آن سیاه‌اند و بعضی سفید. دو خانه مجاورند اگر هر دو سفید باشند و یا مجاور راسی باشند یا مجاور ضلعی. شما دو مهره در این جدول قرار داده‌اید و می‌خواهید با کم‌ترین تعداد حرکت جای این دو مهره را عوض کنید.
شما می‌توانید در یک حرکت هر کدام از مهره‌ها را یا ثابت بگذارید یا به یک خانه مجاور آن ببرید به‌طوری‌که:
شما باید برنامه‌ای بنویسید که با گرفتن ورودی کم‌ترین تعداد حرکت لازم برای جابه‌جا کردن مهره‌ها را به‌دست بیاورد.
در تنها سطر خروجی پاسخ سوال را چاپ نمایید. درصورتی‌که این کار امکان‌پذیر نبود در خروجی $-1$ چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 20 20 AB……………..X XXXXXXXXXXXXXXXXXXX. X…………….XX. .XXXXXXXXXXXXXXXX.X. .XX…………XX.X. .X.XXXXXXXXXXXX.X.X. .X.XX……..XX.X.X. .X.X.XXXXXXXX.X.X.X. .X.X.XX….XX.X.X.X. .X.X.X.XXXX.X.X.X.X. .X.X.X.X.XX.X.X.X.X. .X.X.X.X…XX.X.X.X. .X.X.X.XXXXXX.X.X.X. .X.X.XX……XX.X.X. .X.X.XXXXXXXXXX.X.X. .X.XX……….XX.X. .X.XXXXXXXXXXXXXX.X. .XX…………..XX. .XXXXXXXXXXXXXXXXXX. X………………X | 397 |
| 5 7 X..A..X .XXXXX. .X…XB .XXXXX. X…..X | 12 |
| 20 20 A……………..XX .…………….XXX …………….XXX. ……………XXX.. …………..XXX… ………….XXX…. …………XXX….. ………..XXX…… ……….XXX……. ………XXX…….. ……..XXX……… …….XXX………. ……XXX……….. …..XXX………… ….XXX…………. …XXX………….. ..XXX…………… .XXX……………. XXX…………….. XX……………..B | -1 |