Rezolvare PBinfo #3341

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)