valet

[•mihai.plesa]

Puteti va rog sa-mi dati o idee de rezolvare a problemei de mai jos?
Multumesc!

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

Exemple
valet.in    valet.out    valet.in    valet.out
3 3            imposibil       2 3           7
.#X                             .cX
ccc                             ccc
c#c                                 

   



   

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

[•klamathix]

Tu vrei sa gasesti cel mai scurt drum de la o stare data la o stare ceruta. Pentru asta poti folosi o parcurgere in latime. Gandeste-te doar cum poti retine starile in mod eficient. Daca mai vrei detalii, problema asta e luata de la o runda de F11 de anul trecut gasesti acolo solutiile oficiale.