Enunț

Pe un continent reprezentat printr-o matrice cu n linii și m coloane se află mai multe state, toate în conflict. Astfel, fiecare si-a mobilizat oastea. Fiecare element al matricei reprezintă o regiune.
Două elemente, din matrice, învecinate pe linie sau pe coloană (nu si pe diagonală) reprezintă două regiuni care aparțin aceluiași stat.
Un element din matrice ce contine cifra 0 este o regiune neutră care delimitează statele si nu are soldați.
Elementul ce conține o cifră c nenulă este o regiune ce aparține unui stat și are c soldați.

Cerința

Să se determine numărul S maxim de soldați dintr-un stat al continentului precum și numărul R minim de regiuni pe care le poate avea un stat cu S soldati.

Date de intrare

Fișierul de intrare oaste2.in conține pe prima linie numerele naturale n si m, iar pe fiecare dintre următoarele n linii conține câte m cifre, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire oaste2.out va conține pe prima linie cele două numere S R separate printr-un spațiu, cu semnificația din enunț

Restricții și precizări

n si m vor fi numere naturale cu valori intre 1 si 100 inclusiv;
fiecare element al matricei va avea valori naturale cuprinse intre 0 si 9 inclusiv;
există cel puțin o cifră nenula în matrice

Exemplu

oaste2.in

4 6
0 1 1 0 2 9
9 0 2 0 1 0
0 1 1 0 0 2
0 0 1 1 1 1

oaste2.out

12 3

Explicație

Harta din fișierul de intrare contine 3 state având: 12 soldați (culoarea rosu – 10 regiuni), 12 soldați (culoare galben – 3 regiuni), 9 soldați (culoare verde – 1 regiune)

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema oaste2:

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("oaste2.in");
ofstream g("oaste2.out");
int a[102][102],n,m,s,r;

void citeste()
{
    f>>n>>m;
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            f>>a[i][j];
}
void fill(int i, int j)
{
    s=s+a[i][j];
    r++;
    a[i][j]=0;
    if(a[i-1][j])fill(i-1,j);
    if(a[i][j+1])fill(i,j+1);
    if(a[i+1][j])fill(i+1,j);
    if(a[i][j-1])fill(i,j-1);
}

int main()
{
    citeste();
    int i,j, S=0, R=10001;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(a[i][j])
            {
                r=0; s=0;
                fill(i,j);
                if(s>S)
                {
                    S=s; R=r;
                }
                else
                    if(s==S)R=min(R,r);
            }
    g<<S<<" "<<R<<endl;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3341 oaste2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3341 oaste2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3341 oaste2