== include(page="template/taskheader" task_id="valet") ==
Poveste și cerință...
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.
h2. 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.
h2. Date de intrare
Fișierul de intrare $valet.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $valet.out$ ...
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.
h2. Restricții
Restricții
* $... ≤ ... ≤ ...$
* 1 ≤ n, m ≤ 50
h2. Exemplu
table(example).
|_. valet.in |_. valet.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|_. valet.in |_. valet.out |_. valet.in |_. valet.out |
|3 3
.#X
ccc
c#c
|imposibil
|2 3
.cX
ccc
|7
|
h3. 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
== include(page="template/taskfooter" task_id="valet") ==
