Depozitul cu safeuri personale a băncii Gringotts Ltd are forma unui dreptunghi cu laturile n × m, divizat în n × m platforme pătrate de dimensiunea 1 × 1. Unica platformă liberă este în colțul din stânga sus. Ea marchează ieșirea din depozit. Unele dintre platforme sunt ocupate cu echipamente de supraveghere montate rigid, pe celelalte se află câte un safeu, care are dimensiunea platformei. În unul din safeuri se păstrează Piatra Filozofală. La cererea lui Dumbledore, spiridușii trebuie să scoată din depozit safeul cu Piatra Filozofală. Unica operație pe care o pot efectua ei este deplasarea unui safeu pe o platformă vecină, dacă aceasta este liberă. Se consideră vecine platformele care au o latură comună.
Cerinţă
Scrieți un program care să determine numărul minim de operații necesare pentru a scoate safeul cu Piatra Filozofală din depozit. Safeul se consideră scos din depozit dacă este adus pe platforma de la intrarea în depozit.
Date de intrare
Prima linie a fișierului de intrare safeu.in conține două numere n și m, dimensiunile depozitului. Urmează n linii a câte m simboluri fiecare. Simbolul “.” marchează poziția liberă. Unica poziție liberă este la intrarea în depozit. Simbolul “#” marchează o platformă cu echipament de supraveghere. Platformele cu echipamente de supraveghere nu pot fi deplasate și pe ele nu se plasează safeuri. Simbolul “c” semnifică o platformă cu safeu. Simbolul “X” – platforma pe care se află safeul cu Piatra Filozofală.
Date de ieşire
Dacă safeul nu poate fi scos din depozit, în fișierul de ieșire safeu.out se va înscrie un singur cuvânt Impossible. În caz contrar, unica linie a fișierului va conține un singur număr – numărul minim de operații necesar pentru scoaterea safeului indicat din depozit.
Restricţii
1 ≤ N, M ≤ 50. 1 < N sau 1 < M.
Fiecare dintre simbolurile “.” și “X” apar câte o singură dată.
Simbolul “.” este întotdeauna amplasat în colțul din stânga sus al depozitului.