Roboter vertauschen
Du arbeitest an einem Startup, das versucht, mit Boston Dynamics zu konkurrieren. Eine der Herausforderungen besteht darin, zwei Roboter ihre Plätze auf einem Gitter (Grid) tauschen zu lassen, ohne dass sie sich gegenseitig blockieren.
Das Gitter hat eine Höhe
h und eine Breite w. Der Boden wird durch Punkte (.) gekennzeichnet, und Wände sind durch Rautenzeichen (#) markiert.Die Roboter dürfen sich horizontal, vertikal und diagonal in benachbarte Felder bewegen. Allerdings dürfen sie weder aufeinander noch auf die Wände treten. In jedem Schritt können beide Roboter jeweils entweder einen Zug machen oder auf ihrer aktuellen Position stehenbleiben. Während eines einzelnen Zuges dürfen sie nicht übereinander „hinwegspringen“.
Deine Aufgabe ist es, die minimale Anzahl von Schritten zu ermitteln, die benötigt werden, um den ersten Roboter an die Stelle des zweiten und den zweiten Roboter an die Stelle des ersten zu bringen.
Eingabe
Die erste Zeile der Eingabe enthält 2 Ganzzahlen
h und w (1 ≤ h, w ≤ 50).Die nächsten
h Zeilen bestehen aus je w Zeichen und stellen das Gitter dar.Der erste Roboter ist mit dem Buchstaben
A markiert, der zweite Roboter mit dem Buchstaben B.Ausgabe
Das Programm soll die minimale Anzahl an Schritten ausgeben, die für den Tausch der Roboter erforderlich ist, und
Impossible, falls dies nicht möglich ist.Examples
Input
4 4
AB.#
###.
...#
.###Output
11Input
2 2
AB
..Output
2Input
1 3
A.BOutput
ImpossibleConstraints
Time limit: 15 seconds
Memory limit: 512 MB
Output limit: 1 MB