Problem description

Jasio w starym Ubuntu odnalazł bardzo ciekawą i chyba trudną grę: Klotski (w pakiecie gnome-klotski). Gra polega na tym, aby na małej planszy bardzo zapełnionej klockami wyprowadzić główny klocek poza planszę. Niestety nie jest to łatwe, bo miejsca jest mało…

W żadnym momencie gry, klocki nie mogą na siebie nachodzić. Klocków nie można obracać, ani rozrywać, a jedynie wolno je przesuwać w dół, górę, prawo lub lewo i tylko i wyłącznie na wolne pola. Klocki nie muszą być prostokątami, ale zawsze stanowią spójną część.

Celem gry jest położyć klocek główny tak, aby zakrywał on wszystkie pola docelowe. Jedynie klocek główny może znaleźć się na polach docelowych, dla pozostałych klocków te pola są niedostępne. Oczywiście cel gry należy osiągnąć w jak najmniejszej liczbie ruchów. Za ruch uznaje się tutaj przesunięcie jednego wybranego klocka o jedną jednostkę.

Napisz program, który: wczyta konfigurację początkową gry Klotski, wyznaczy minimalną liczbę ruchów niezbędnych do przejścia gry i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M, oddzielone pojedynczym odstępem, określające kolejno wysokość i szerokość planszy.

W kolejnych N wierszach znajduje się po M znaków – opis planszy. Klocki, których nie można przesunąć oznaczone są znakami #. Klocek główny oznaczony jest znakami @. Pola docelowe oznaczone są znakami wykrzyknika !. Pole wolne, na którym nie stoi żaden klocek oznaczone jest znakiem kropki .. Pozostałe klocki oznaczane są wielkimi literami alfabetu angielskiego. Te same litery przyporządkowane są tym samym klockom, zaś różne litery – różnym klockom.

Gwarantowane jest, że testy zawierają tylko zagadki możliwe do rozwiązania.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę naturalną – minimalną liczbę ruchów niezbędnych do zakrycia wszystkich pól docelowych klockiem głównym.

Ograniczenia

3 ≤ N, M ≤ 6, N ⋅ M ≤ 25.

Przykład

3 3
@A!
BAC
#D.

4

6 4
A@@B
A@@B
CDDE
FGHI
J..K
#!!#

57