# PBinfo #395 – Comori – Rezolvare C++

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

## Enunț

Cerinţa
Ali Baba și cei 40 de hoți stăpânesc un deșert de formă dreptunghiulară, împărțit în n linii și m coloane, care definesc n*m sectoare. În fiecare sector se află o  comoară ascunsă de Ali Baba. Se cunoaște valoarea în galbeni a fiecărei comori.

Un călător trebuie să traverseze deșertul de la Nord la Sud, trecând dintr-un sector  în altul, astfel: din sectorul (i j)  se poate ajunge în unul din sectoarele (i+1,j-1), (i+1,j) sau (i+1,j+1), dar fără a părăsi deșertul (ar fi omorât de oamenii lui Ali Baba). La trecerea printr-un sector, călătorul colectează comoara din acel sector.

Determinați valoarea totală maximă a comorilor pe care le poate colecta călătorul la traversarea deșertului, știind că pleacă din orice sector al liniei 1 (Nord) și se oprește în orice sector al linei n (Sud), cu respectarea condițiilor de mai sus.

Date de intrare
Fişierul de intrare comori.in conţine pe prima linie numerele n m. Următoarele n linii conțin câte m numere naturale, reprezentând valorile comorilor din fiecare sector.

Date de ieşire
Fişierul de ieşire comori.out va conţine pe prima linie numărul V, reprezentând valoarea maximă a comorilor care pot fi colectate.

Restricţii şi precizări

1 ≤ n,m ≤ 200
valoarea fiecărei comori este un număr natural mai mic decât 100

Exemplu:
comori.in

4 5
5 8 3 7 7 
1 1 4 5 1 
5 8 9 1 7 
5 8 6 6 9 
comori.out

29
Explicație
Un traseu prin care se colectează comori în valoare de 29 galbeni este:



 5 
 8 
 3 
7 
 7 


 1 
 1 
 4 
5 
 1 


 5 
 8 
9 
 1 
 7 


 5 
8 
 6 
 6 
 9 


 .tbl-traseu td{ 	padding: 5px; border: solid 1px gray; }

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;
#define NN 205
ifstream fin("comori.in");
ofstream fout("comori.out");
int n, m, a[NN][NN], s[NN][NN];
int Maxim(int x , int y){
	return x>y ? x : y;
}
int Maxim(int x, int y, int z)
{
	return Maxim(Maxim(x , y) , z);
}
int Maxim(int * v, int * u)
{
	int M = *v;
	for( v++; v!=u; v++)
		M = Maxim(M,*v);
	return M;
}
int main(){
	assert(fin >> n >> m);
	for(int i=1 ; i<=n ; ++i)
		for(int j=1 ; j<=m ; j++)
			assert(fin >> a[i][j]);
	for(int j=1;j<=m;++j)
		s[1][j] = a[1][j];
	for(int i=2; i<=n;++i){
		s[i][1] = a[i][1] + Maxim(s[i-1][1], s[i-1][2]);
		s[i][m] = a[i][m] + Maxim(s[i-1][m-1],s[i-1][m]);
		for(int j=2 ; j<m ; ++j)
			s[i][j] = a[i][j] + Maxim(s[i-1][j-1] , s[i-1][j] , s[i-1][j+1]);
	}
	fout << Maxim(s[n]+1, s[n]+m+1) ;
	return 0;
}
```

## Resurse

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