# PBinfo #4081 – alpinistii – Rezolvare C++

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

## Enunț

Enunț
Un grup de alpiniști, aflați pe marginea unei stânci de pe un versant, sunt prinși în mijlocul unei furtuni. Pentru a se adăposti, ei trebuie să găsească o zonă-adăpost din versant formată din spații sigure învecinate în direcțiile N, E, S și V, suficient de mare, astfel încât în ea să se poată adăposti întregul grup.  Alpiniștii au, pe căștile lor, montate camere care trimit o filmare video, în direct, la o echipă de programatori salvamontiști. Informaticienii reușesc să analizeze spațiile sigure ale versantului și să reprezinte versantul cu ajutorul unei matrice binare. Fiecare spațiu sigur este codificat cu 0, iar valorile de 1 reprezintă spațiile blocate.
Ei vă cer ajutorul pentru a reuși să-i salveze pe alpiniști.

Cerința
Cunoscând matricea binară ce codifică versantul, determinați:
1) Numărul maxim de spații sigure ce pot forma o zonă-adăpost de pe versant
2) Numărul maxim de spații sigure dintr-o zonă-adăpost dreptunghiulară corespunzătoare unui dreptunghi format doar din valori de 0 din matricea dată.

Date de intrare
Fișierul de intrare alpinistii.in conține pe prima linie trei numere naturale: c, n și m, separate prin câte un spațiu, c reprezentând numărul cerinței ce urmează a fi rezolvată (1 sau 2), n reprezentând numărul de linii ale matricei, iar m numărul de coloane. Fiecare dintre următoarele n linii conține câte m cifre de 0 și 1, separate prin câte un spațiu, cu semnificația din enunț.

Date de ieșire
Fișierul de ieșire alpinistii.out va conține pe prima linie un număr natural reprezentând răspunsul la cerința care se rezolvă.

Restricții și precizări

1 ≤ n ≤ 200
1 ≤ m ≤ 200
în matrice sunt doar valori de 0 și 1
Pentru rezolvarea corectă a cerinței 1 se acordă 40 puncte, iar pentru cerința 2 se acordă 60 puncte.

Exemplu 1:
alpinistii.in

1
7 8
1 1 1 1 1 1 1 1 
1 0 0 1 1 1 1 0 
1 1 0 1 0 0 0 1 
1 1 0 1 0 0 1 1 
0 1 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
1 0 0 1 1 1 1 1
alpinistii.out

13
Explicație


Zona-adăpost înconjurată cu galben este cea mai mare posibilă (13 spații sigure), celelalte zone-adăpost au: 5 spații sigure (verde), 4 spații sigure (maro) și 1 spațiu sigur (albastru).

Exemplu 2:
alpinistii.in

2
7 8
1 1 1 1 1 1 1 1 
1 0 0 1 1 1 1 0 
1 1 0 1 0 0 1 1 
1 1 0 1 0 0 0 1 
0 1 1 0 0 0 0 1 
0 0 1 0 0 0 0 1 
1 0 0 1 1 1 1 1
alpinistii.out

9
Explicație


Numărul maxim de spații sigure ce formează o zonă-adăpost dreptunghiulară este 9 (zona înconjurată cu galben). Se observă că matricea conține și alte două zone dreptunghiulare formate din câte 8 spații sigure (zonele inconjurate cu maro și verde).

## Cod sursă C++

```cpp
///autori Ivan Andrei & Hangu Calin
#include <fstream>
#include <queue>
#include <stack>
using namespace std;
ifstream in ("alpinistii.in");
ofstream out ("alpinistii.out");
const int max_size = 2e2 + 1, max_dir = 4;
/// 2e2 = 2 * 10 ^ 2
int a[max_size][max_size], dr[max_size], st[max_size], h[max_size], n, m, c, total, rez,
di[] = {-1, 0, 1, 0},
dj[] = {0, 1, 0, -1};
queue <pair <int,int> > coada;
stack <int> stiva;
void umplere (int is, int js)
{
    /// nu este neaparata nevoie de implementarea algoritmului de fill adaptat din Lee
    total++;
    a[is][js] = 1;
    coada.push(make_pair(is, js));
    while (!coada.empty())
    {
        int i = coada.front().first, j = coada.front().second;
        for (int k = 0; k < max_dir; k++)
        {
            int iv = i + di[k], jv = j + dj[k];
            if (iv > 0 && jv > 0 && iv <= n && jv <= m && a[iv][jv] == 0)
            {
                a[iv][jv] = 1;
                total++;
                coada.push(make_pair(iv, jv));
            }
        }
        coada.pop();
    }
}
void calc_st ()
{
    /// ne asiguram ca stiva este vida
    while (!stiva.empty())
    {
        stiva.pop();
    }
    for (int j = 1; j <= m; j++)
    {
        ///cat timp avem elemente in varful stivei care sunt mai mari decat elementul curent le eliminam pana cand stiva devine vida sau varful stivei este mai mic decat elementul curent
        while (!stiva.empty() && h[stiva.top()] >= h[j])
        {
            stiva.pop();
        }
        ///daca stiva este vida ==> elementul curent este minim pe tot vectorul din partea stanga
        if (stiva.empty())
        {
            st[j] = 0;
        }
        ///in caz contrar limita din stanga a secventei pe care elemntul curent este minim va deveni varful stivei
        else
        {
            st[j] = stiva.top();
        }
        ///adaugam indicele
        stiva.push(j);
    }
}
void calc_dr ()
{
    while (!stiva.empty())
    {
        stiva.pop();
    }
    /// ne asiguram ca stiva este vida
    for (int j = m; j > 0; j--)
    {
        ///cat timp avem elemente in varful stivei care sunt mai mari decat elementul curent le eliminam pana cand stiva devine vida sau varful stivei este mai mic decat elementul curent
        while (!stiva.empty() && h[stiva.top()] >= h[j])
        {
            stiva.pop();
        }
        ///daca stiva este vida ==> elementul curent este minim pe tot vectorul din partea dreapta
        if (stiva.empty())
        {
            dr[j] = m + 1;
        }
        ///in caz contrar limita din dreapta a secventei pe care elemntul curent este minim va deveni varful stivei
        else
        {
            dr[j] = stiva.top();
        }
        ///adaugam indicele
        stiva.push(j);
    }
}
void citire ()
{
    in >> c >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            in >> a[i][j];
        }
    }
}
void cerinta1 ()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            /// facem fill pentru fiecare 0 pe care il gasim
            /// in matrice si det. aria zonei care contine acel 0
            if (a[i][j] == 0)
            {
                umplere(i, j);
                rez = max(rez, total);
                total = 0;
            }
        }
    }
}
void cerinta2 ()
{
    for (int i = 1; i <= n; i++)
    {
        /// calculam cate celule consecutive sunt cu valori
        /// de 0 deasupra elementului pe care il verificam, incepand cu elementul curent
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 1)
            {
                h[j] = 0;
            }
            else
            {
                h[j]++;
            }
        }
        /// algoritm de tip ”Skyline”
        /// calculam capetele secventei de lungime maxima
        /// in care h[j] este minim
        /// lungimea secventei va reprezenta cea de - a doua
        /// latura a dreptunghiului nostru
        calc_st();
        calc_dr();
        for (int j = 1; j <= m; j++)
        {
            rez = max(rez, h[j] * (dr[j] - st[j] - 1));
        }
    }
}
void afisare ()
{
    out << rez;
}
int main ()
{
    citire();
    if (c == 1)
    {
        cerinta1();
    }
    else
    {
        cerinta2();
    }
    afisare();
    in.close();
    out.close();
    return 0;
}
```

## Resurse

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