Az őrült király

Péter király az A királyságban él, a lánya pedig a B királyságban. A király kapott egy levelet, amely szerint a lánya gyermeknek adott életet. A király alig várja, hogy láthassa az unokáját! Ez azonban sajnos nem olyan egyszerű.

Az A és B királyságokat egy erdő választja el egymástól. Az erdő tele van ellenséggel, akikkel a király nem szívesen találkozna. Ha megtámadják a királyt a B királyságba vezető útja során, akkor soha többé nem láthatja az unokáját és a lányát a támadás halálos következményei miatt.

A király Biztonsági Tanácsa rendelkezik információkkal az ellenség helyzetéről, és ez megkönnyíti a király dolgát. Valamilyen ismeretlen okból kifolyólag az erdő egy M×N-es sakktábla. (M a sorok, N az oszlopok száma, 1 ≤ M, N ≤ 100.)

A király ellenségei az alábbi ábrán látható módon tudnak lóval közlekedni. A lovak általában ugyanúgy haladnak (vagy ugranak), mint a sakkban. A király sajnos nem tud repülőre ülni, hogy eljusson az A pontból a B pontba, mivel a repülőt még nem találták fel. Így ugyanúgy közlekedik, ahogy a sakkbeli királyok (a részletekért lásd az ábrát).

A király nem léphet egy X mezőre, ha azt a mezőt az ellenség lova foglalja. Amíg a király mozog, a lovak nem, de ha van legalább egy ló, amelyik egy lépésen belül el tudja érni az X mezőt, akkor a király nem léphet oda (kivéve ha az X mező vagy az A, vagy a B királyság).

Te vagy az A királyság Elektronikus Hírszerzésének főnöke (apropó, a számítógépet már feltalálták), és arra kértek, hogy add meg az A királyságból a B királyságba vezető legrövidebb útvonal L hosszát, a király ugyanis nem tud tovább várni.

A bemenet specifikációja

A bemenet első sora T-t, a tesztesetek számát tartalmazza (T ≤ 100). Minden teszteset első sora két számból, M-ből és N-ből áll. Ezután M sor következik, amelyek mindegyike N szimbólumot tartalmaz az S = {„.”, „Z”, „A”, „B”} halmazból. A „.” egy szabad mezőt jelöl. A „Z” azt jelenti, hogy az adott mezőn egy ló áll. Az „A” az A királyságot, a „B” pedig a B királyságot jelöli. Minden teszteset pontosan egy A királyságot és egy B királyságot tartalmaz.

A kimenet specifikációja

Minden tesztesetre meg kell határozni az L értéket, és a kimenetre kell írni egy sort a „Minimal possible length of a trip is L” szöveggel, ha a király el tudja érni a B királyságot. „L” helyére a megfelelő értéket kell behelyettesíteni. Ha a király nem tud biztonságban eljutni a B királyságba, akkor egy „King Peter, you can't go now!” tartalmú sort kell kiírni.

Példa bemenet

1. 4
2. 5 5
3. .Z..B
4. ..Z..
5. Z...Z
6. .Z...
7. A....
8. 3 2
9. ZB
10. .Z
11. AZ
12. 6 5
13. ....B
14. .....
15. .....
16. ..Z..
17. .....
18. A..Z.
19. 3 3
20. ZZ.
21. ...
22. AB.

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. King Peter, you can't go now!
2. Minimal possible length of a trip is 2
3. King Peter, you can't go now!
4. Minimal possible length of a trip is 1

letöltés szöveges állományként