# PBinfo #2741 – SAO1 – Rezolvare C++

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

## Enunț

După ce ți-ai dat seama că nu poți învinge nici unul dintre monștrii (din problema SAO), ai decis să te retragi și să devii un fermier. Din banii pentru cumpărarea echipamentului ai cumpărat o parcelă codificată sub forma unei matrice de n linii și m coloane, pentru fiecare zonă cunoscându-se fertilitatea ei. Cum nu ai bani ca să cultivi pământul, dorești să selectezi o parcelă în care toate zonele să aibă aceeași fertilitate, iar fertilitatea totală să fie maximă. Fertilitatea totală a unei parcele este egală cu suma fertilităților zonelor care compun acea parcelă.

Cerința
Dându-se matricea codificărilor zonelor din teren, să se determine fertilitatea totală maximă a unei parcele în care  toate zonele au aceeași fertilitate.

Date de intrare
Fișierul de intrare sao1.in conține pe prima linie numerele n şi m, iar pe următoarele n linii câte m numere naturale, separate prin spaţii, reprezentând elementele matricei.

Date de ieșire
Fișierul de ieșire sao1.out va conține numărul P, reprezentând fertilitatea totală maximă a unei parcele, în condițiile date.

Restricții și precizări

1 ≤ n,m ≤ 500
fertilitatea parcelelor și fertilitatea totală se va încadra pe tipul de date long long.
nu există sol infertil (a cărui fertilitate să fie mai mică sau egală cu 0).
acesta este “bad ending”-ul problemei SAO

Exemplu 1:
sao1.in

4 4
1 1 1 3
1 1 1 3
1 1 1 3
3 3 3 3
sao1.out

21
Explicație
Cele 7 valori de 3 formează zona cu profit maxim.

Exemplu 2:
sao1.in

4 4
3 5 1 3
1 5 5 3
5 5 5 3
3 3 3 3
sao1.out

30
Explicație
Cele 6 valori de 5 formează zona cu profit maxim.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sao1.in");
ofstream fout("sao1.out");
long long a[502][502],n,m,s,smax;
void refill(int x,int y,long long v){
    a[x][y]=0;
    s+=v;
    if(a[x+1][y]==v){
        refill(x+1,y,v);
    }
    if(a[x-1][y]==v){
        refill(x-1,y,v);
    }
    if(a[x][y+1]==v){
        refill(x,y+1,v);
    }
    if(a[x][y-1]==v){
        refill(x,y-1,v);
    }
}
int main(){
    fin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]){
                s=0;
                refill(i,j,a[i][j]);
                smax=max(smax,s);
            }
        }
    }
    fout<<smax;
    return 0;
}
```

## Resurse

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