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.

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)

#include <bits/stdc++.h>
using namespace std;

ifstream cin("oaste2.in");
ofstream cout("oaste2.out");

int n, m, a[101][101], c, sum, cmin = 1000000, smax = 0;

bool inmat(int i, int j){
    return i >= 1 && j >= 1 && i <= n && j <= m;
}

int di[]={0,0,-1,1}, dj[]={-1,1,0,0};

void fill(int i, int j){
    c++;
    sum += a[i][j];
    a[i][j] = 0;
    for(int d = 0; d < 4; ++d){
        int inou = i + di[d];
        int jnou = j + dj[d];
        if(inmat(inou, jnou) && a[inou][jnou])
            fill(inou, jnou);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> a[i][j];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(a[i][j]){
                c = 0, sum = 0;
                fill(i,j);
                if(sum > smax)
                    smax = sum, cmin = c;
                else if(sum == smax && c < cmin)
                    cmin = c;
            }
    cout << smax << ' ' << cmin;
    return 0;
}