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


Problema  INDRAGOSTITILOR

 Doi indragostiti numiti R si J sunt pedepsiti pentru faptul ca 
nu au obtinut rezulate satisfacatoare in procesul de invatamant
si in activitatea practica, rezultate atat de necesare unei societati 
aflata in plin proces de tranzitie catre Economia de Piata.

 Prin urmare, sunt inchisi intr-un labirint L codificat ca o matrice 
binara cu n linii si m coloane. 
 Elementele L(i,j) sunt camere.
 
 Codificarea labirintului se face in felul urmator:

         1, daca camera este inaccesibila;
 L(i,j)=
         0, in cazul in care aceasta este accesibila.


 Daca unul dintre indragostiti se afla intr-o camera, 
acesta poate intra in oricare din camerele situate 
la nord, sud, est, vest, cu conditia ca aceasta sa fie ACCESIBILA.
 Fiind date camerele in care se gasesc R si J, se cere sa se determine
timpul minim si traseele urmate de cei doi astfel incat, in final, amandoi 
sa se gaseasca in aceeasi camera. In fiecare unitate de timp, oricare 
din indragostiti poate intra intr-o camera invecinata accesibila sau poate
ramane pe loc.
 In fisierul text REGASIRE.IN se afla un set de date de test, cu structura:

 linia 1:   m  n
 linia 2:   i1, j1  { coordonatele camerei in care se afla R}
 linia 3:   i2, j2  {coordonatele camerei in care se afla J}
 pe urmatoarele m linii se afla matricea binara.

 Programul va afisa traseul optim al celor doi (daca exista un traseu), atat
in fisierul text REGASIRE.OUT cat si pe monitor, ca in exemplul de mai jos, 
pentru care intrarea este:
  
 linia 1:  3  3
 linia 2:  1  1
 linia 3:  1  3
 linia 4:  0 1 0
 linia 5   0 0 0
 linia 6   0 0 0.

   Afisarea:

 timpul 0:

 R1J
 000
 000

  timpul 1:

  010
  R0J
  000
  
 timpul 2:

  010
  0?0
  000

Observatii:
 1) Cuvintele linia, numarul ei nu sunt trecute in fisier.
 2) Dupa afisarea unei configuratii se asteapta apasarea unei
 taste pentru continuare ( putina mila fata de corector!).  
 3) Camera de intalnire va fi marcata in configuratia finala
 prin "?".  
 4) 1 <= n <= 10, 1 <= m <= 10

Punctaj: 66,6666666666666666666666666666666666666666666666666(6).  
 

 




 
 
