# PBinfo #4004 – Alpinist1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Harta unui munte este reprezentată printr-o matrice cu n linii și m coloane în care fiecare element reprezintă înălțimea zonei respective. Un alpinist pleacă de la coordonatele (1,1) și dorește să ajungă la coordonatele (n,m). Deplasarea se face pe aceeași linie sau coloană; alpinistul poate să treacă din zona curentă în zona învecinată numai dacă înălțimea zonei curente este mai mică sau egală cu cea a zonei învecinate.

Determinați lungimea minimă a unui traseu al alpinistului.

Date de intrare
Programul citește de la tastatură numerele n m, apoi n*m numere naturale, reprezentând harta muntelui.

Date de ieșire
Programul va afișa pe ecran numărul L, reprezentând lungimea minimă a unui traseu al alpinistului.

Restricții și precizări

1 ≤ n,m ≤ 20;
înălțimile zonelor fi mai mici decât 100;
alpinistul nu poate părăsi muntele și nu poate trece de două ori prin aceeași zonă;
dacă nu există niciun traseu se va afișa imposibil.

Exemplu:
Intrare

4 5
4 5 3 8 9
8 7 7 8 9
9 7 3 9 10
2 5 4 10 11
Ieșire

8
Explicație
Un traseu de lungime minimă este:

1 2 - - -
- 3 4 5 6
- - - - 7
- - - - 8

## Cod sursă C++

```cpp
#include <iostream>
#include <iomanip>
using namespace std;
int n , m , A[21][21], T[21][21], lgmin;
const int di[]={0,0,1,-1}, dj[]={1,-1,0,0};
bool OK(int i ,int j , int H)
{
	if(i < 1 || i > n || j < 1 || j > m)
		return false;
	if(T[i][j] != 0)
		return false;
	if(A[i][j] < H)
		return false;
	return true;
}
void Back(int i , int j , int pas)
{
	T[i][j] = pas;
	if(i == n && j == m)
	{
		if(pas < lgmin)
			lgmin = pas;
	}
	else
		for(int k = 0 ; k < 4 ; k ++)
		{
			int iv = i + di[k], jv = j + dj[k];
			if(OK(iv , jv, A[i][j]))
				Back(iv , jv , pas + 1);
		}
	T[i][j] = 0;
}
int main()
{
	cin >> n >> m;
	for(int i = 1;  i <= n ; i ++)
		for(int j = 1 ; j <= m ; j ++)
			cin >> A[i][j];
	lgmin = n * m + 1;
	Back(1 , 1 , 1);
	if(lgmin == n * m + 1)
		cout << "imposibil" << endl;
	else
		cout << lgmin << endl;
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4004)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4004/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4004/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)