# PBinfo #1461 – Meteoriti – Rezolvare C++

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

## Enunț

Din cauza blestemelor dușmanilor, asupra plantației de ‘noledge a vrăjitorului Arpsod s-a năpustit o ploaie de…meteoriți. Plantația vrăjitorului e foarte bine delimitată: aceasta are forma unei matrice cu N linii și M coloane, iar în fiecare celulă era plantat câte un fir de ‘noledge. Din motive clare de răzbunare, dușmanii nu s-au mulțumit cu o singură ploaie, astfel, pe plantația vrăjitorului au căzut meteoriți în mai multe reprize. La fiecare repriză, pe fiecare celulă a unui dreptunghi bine delimitat, au căzut exact C meteoriți. După ce ploaia s-a oprit, pe fiecare celulă se afla un “bloc” de piatră de înălțime egală cu numărul meteoriților căzuți în acea celulă. Arpsod, foarte furios, a luat următoarea decizie: va construi un laborator exact peste meteoriții căzuți, de unde își va pedepsi dușmanii. El a hotărât că cel mai bun amplasament pentru acest laborator este la înălțime maximă. Totodată, el își dorește ca laboratorul lui să aibă o suprafață cât mai mare.

Cerința
Deoarece Arpsod şi arhitectul său, Ierdnac, sunt prea ocupaţi să pregătească schița viitorului laborator, vă roagă pe voi să determinați aria maximă a unei suprafețe cu celule învecinate, de înălțime maximă precum și numărul de fire de ‘noledge rămase neatinse după căderea meteoriților ( poate au ratat vreunu’ ! ).

Date de intrare
Pe prima linie a fișierului meteoriti.in se află trei numere naturale separate prin spațiu: N și M, reprezentând dimensiunile plantației și R, reprezentând numărul de reprize de meteoriți. Pe următoarele R linii se vor afla cinci valori separate prin spațiu: r1 c1 r2 c2 C, unde r1 c1 reprezintă coordonatele colțului stânga sus ( linie coloană ) iar r2 c2 coordonatele colțului dreapta jos ( linie coloană ) ale dreptiunghiului pe care vor cădea meteoriți iar C reprezintă numărul de meteoriți ce vor cădea pe fiecare celulă din cele delimitate.

Date de ieșire
În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.

Restricții și precizări

4 ≤ N, M ≤ 2.000
1 ≤ R ≤ 100.000
1 ≤ r1 ≤ r2 ≤ N
1 ≤ c1 ≤ c2 ≤ M
1 ≤ C ≤ 20.000
Două celule se consideră vecine dacă au cel puțin o latură comună.
Înălțimea inițială a celulelor se consideră 0.
Se garantează că pentru 30% din teste 4 ≤ N, M ≤ 300 și 1 ≤ R ≤ 300
Pentru rezolvarea corectă a primei cerinţe se acordă 80% din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerinţe se acordă 20% din punctajul pe testul respectiv
Fișierul de ieșire TREBUIE să conțină exact DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
Dacă îi veți da răspunsul corect vrăjitorului, acesta vă va primi și pe voi prin laboratorul său.
NU este bine să îl supărați pe vrăjitor!

Exemplu:
meteoriti.in

5 6 7
2 2 4 3 1
4 4 4 6 2
1 5 4 6 1
2 5 3 6 1
2 3 4 3 1
5 1 5 3 3
4 2 4 2 1
meteoriti.out

3 12
Explicație
Matricea după meteoriţi:
0 0 0 0 1 1
0 1 2 0 2 2
0 1 2 0 2 2
0 2 2 2 3 3
3 3 3 0 0 0

Înălțimea maximă este 3 iar aria maximă a unei suprafețe de înălțime 3 este tot 3

## Cod sursă C++

```cpp
/*  Implementare: Cristi Dospra
	Punctaj: 100p
	Utilizat: Mars + Fill(cu coada) + fstream
	Complexitate: O( N*M + R )
*/
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
#define Nmax 2002
ifstream fin ( "meteoriti.in" );
ofstream fout ( "meteoriti.out" );
int Mars[Nmax][Nmax], Nr, N, M, R;
bool viz[Nmax][Nmax];
const int dir[4][2] = { { -1,0 }, { 0,1 }, { 1,0 }, { 0,-1 } };
queue < pair < int , int > > Q;
bool Inside ( int x, int y ){
    if ( x > 0 && x <= N && y > 0 && y <= M )
        return 1;
    return 0;
}
void Fill ( int x, int y, int h ){
    Q.push ( make_pair(x,y) );
    viz[x][y] = 1;
    while ( !Q.empty() ){
        int x = Q.front().first;
        int y = Q.front().second;
        Nr++;
        Q.pop();
        for ( int i = 0; i < 4; ++i ){
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if ( Inside ( xx, yy ) && !viz[xx][yy] && Mars[xx][yy] == h ){
                Q.push ( make_pair(xx, yy) );
                viz[xx][yy] = 1;
            }
        }
    }
}
int main(){
    fin >> N >> M >> R;
    int x1, y1, x2, y2, c;
    while ( R-- ){
        fin >> x1 >> y1 >> x2 >> y2 >> c;
        Mars[x1][y1] += c;
        Mars[x2+1][y1] -= c;
        Mars[x1][y2+1] -= c;
        Mars[x2+1][y2+1] += c;
    }
    for ( int i = 1; i <= N; ++i )
        for ( int j = 1; j <= M; ++j )
            Mars[i][j] += Mars[i-1][j] + Mars[i][j-1] - Mars[i-1][j-1];
    int MaxArea = -1, MaxHeight = -1, UnTouched = 0;
    for ( int i = 1; i <= N; ++i ){
        for ( int j = 1; j <= M; ++j ){
            if ( !viz[i][j] ){
                Nr = 0;
                Fill ( i, j, Mars[i][j] );
                if ( Mars[i][j] == 0 )
                    UnTouched += Nr;
                else{
                    if ( Mars[i][j] > MaxHeight ){
                        MaxHeight = Mars[i][j];
                        MaxArea = Nr;
                    }
                    else if ( Mars[i][j] == MaxHeight && Nr > MaxArea )
                        MaxArea = Nr;
                }
            }
        }
    }
    fout << MaxArea << " " << UnTouched;
    return 0;
}
```

## Resurse

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