Fișierul intrare/ieșire	valet.in, valet.out	Sursă	.campion 2011
Autor	Emanuela Cerchez	Adăugată de	Calin Stefan Georgescu • calingeorgescu
Timp de execuție pe test	1.4 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Valet (clasele 7-8)

Vasile lucrează într-o parcare. Sarcina lui este să scoată mașinile clienților din parcare.
Terenul de parcare este dreptunghiular, format din nxm zone identice, aranjate pe n linii și m coloane. Liniile sunt numerotate de la 1 la n, iar coloanele de la 1 la m. Ieșirea din parcare este în colțul parcării cu coordonatele (1,1).
În fiecare zonă se poate afla o mașină, un stâlp sau poate fi liberă. Parcarea este plină, singura zonă liberă fiind ieșirea din parcare. Prin urmare, este foarte complicat să scoți o mașină din parcare. Pentru a-și face loc, Vasile poate muta o mașină din zona în care este plasată în una dintre zonele învecinate, dacă aceasta este liberă.
Evident, stâlpii nu pot fi mutați, doar mașinile.
Două zone sunt învecinate dacă se află pe aceeași linie pe coloane consecutive sau pe aceeași coloană, pe linii consecutive.

Cerință

Scrieți un program care să determine numărul minim de mutări de mașini pe care trebuie să le execute Vasile pentru a scoate o mașină din parcare, dacă acest lucru este posibil.

Date de intrare

Fișierul de intrare valet.in conține pe prima linie numerele naturale n și m separate prin spațiu. Urmează n linii fiecare conținând câte m caractere din mulțimea {‘.’, ‘#’, ‘c’, ‘X’}.
Caracterul ‘.’ indică zona liberă.
Caracterul ‘#’ indică un stâlp.
Caracterul ‘c’ indică o mașină parcată.
Caracterul ‘X’ indică mașina pe care Vasile trebuie să o scoată din parcare.
În fișierul de intrare există un singur caracter ‘X’ și un singur caracter ‘.’, plasat în colțul (1,1) al parcării.

Date de ieșire

Fișierul de ieșire valet.out va conține o singură linie pe care va fi scris numărul minim de mutări pe care trebuie să le efectueze Vasile pentru a scoate mașina din parcare, dacă acest lucru este posibil. În caz contrar pe prima linie se va scrie cuvântul imposibil.

Restricții

• 1 ≤ n, m ≤ 50

Exemplu

Explicație
Cele 7 mutări din al doilea exemplu sunt:
(1,2) ->(1,1)
c.X
ccc
(1,3)->(1,2)
cX.
ccc
(2,3)->(1,2)
cXc
cc.
(2,2)->(2,3)
cXc
c.c
(2,1)->(2,2)
cXc
.cc
(1,1)->(2,1)
.Xc
ccc
(1,2)->(1,1)
X.c
ccc