
		PROBLEMA:

	O regiune desertica este reprezentata printr-un tablou de dimensiune mxn, m<=100, n<=100.
Elementele tabloului sunt numere naturale mai mici decat 255, reprezentand diferentele de nivel
fata de nivelul marii (cota zero).

	Sa se stabileasca:

	(a) Un traseu pentru a traversa desertul de la Nord la Sud (de la linia 1 la linia m) astfel:
	
	- se porneste dintr-un punct al liniei 1;
	- deplasarea se face in una din directiile E,SE,S,SV,V
	- suma diferentelor de nivel (la urcare si la coborare) sa fie minima

	(b) Un traseu pentru a traversa desertul de la Nord la Sud in conditiile punctului (a), la
care adaugam conditia :
	- lungimea traseului sa fie minima

	Fisierul de intrare DESERT.TXT contine mai multe seturi de date separate prin caracterul *,
fiecare avand urmatoarea structura:

linia 1:	m,n
linia 2:
....		elementele tabloului (pe linii) separate prin spatii
....
linia m:

	Fisierul de iesire TRASEU.TXT va contine pentru fiecare set de date:
(a)
TRASEU: (i1,j1) (i2,j2) ... (ip,jp)
(b)
TRASEU: (i1,j1) (i2,j2) ... (ik,jk)

EXEMPLU:

DESERT.TXT
4 4
1 4 4 3
5 50 75 4
6 5 4 4
6 5 1 10
*

TRASEU.TXT
(a)
TRASEU: (1,3) (2,4) (3,4) (3,3) (4,2)
(b)
TRASEU: (1,2) (2,1) (3,2) (4,2)

SOLUTIE:
--------

	Se foloseste PD. Daca n-ar fi permise deplasarile la stanga si la dreapta, problema ar fi
banala. Pentru a rezolva situatia cand aceste deplasari sunt permise, s-a folosit o idee similara
cu cea din algoritmul Floyd. Spre deosebire de aceasta (complexitate de ordinul n^6), prin algo-
ritmul nostru obtinem o solutie de complexitate n^3.
	Sa presupunem ca am rezolvat problema pt. k linii (am determinat drumurile de lungime mi-
nima de la prima linie la toate elementele de pe linia k) si vom determina linia k+1 pornind de
la linia precedenta, considerand pt. inceput doar deplasarile in jos,jos-stanga,jos-dreapta. In
continuare, aceasta linie va fi actualizata de n ori dupa cum urmeaza:
- pt. fiecare element de pe linia k+1 verificam daca este mai eficienta o legatura de la stanga
sau de la dreapta; daca da, actualizam acea pozitie.