OLIMPIADA NATIONALA DE INFORMATICA				SUCEAVA - 1996
CLASA A XI-A							25 martie


Problema TRANSFORMARI

   Fie o tabla de joc formata din nxm casute asezate pe n linii si m coloane.
Casutele pot fi ocupate sau nu cu piese de diverse culori: A, B, C, ... .
   Dandu-se o configuratie, se cere sa se precizeze un sir de transformari prin
care se ajunge la alta configuratie data. O transformare consta din mutarea unei
piese. O piesa poate fi mutata sus, jos, stanga sau dreapta, daca in directia 
respectiva exista o casuta libera.

INTRAREA: In fisierul text T.IN va fi un set de date, avand urmatoarea
structura

n m
linie vida
configuratia initiala
linie vida
configuratia finala

ca in exemplul urmator:

3 4

-AAA
BABB
CBC-

AAAA
BBBB
CC--

IESIREA: Fisierul text T.OUT contine mutarile necesare pentru a transforma
intrarea in iesirea ceruta, dupa modelul de mai jos (vezi obs.4).

Pentru exemplul precedent, o iesire posibila este:

1 2   1 1
2 2   1 2
3 2   2 2
3 3   3 2

OBSERVATII:
1. Seturile de date sunt corecte.
2. Intotdeauna exista solutie; daca exista mai multe, se va afisa doar una.
3. Semnificatia caracterului '-' din intrare este "casuta libera".
4. Semnificatia unei linii

i j   p q

din iesire este: " din casuta de coordonate (i,j) se trece in casuta de
coordonate (p,q)", unde prin coordonate intelegem indicele de linie
respectiv de coloana.
5. 2 <= n <= 6,
   2 <= m <= 6,
   sunt cel putin 2 casute libere.