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
sim
vor fi numere naturale cu valori intre1
si100
inclusiv;- fiecare element al matricei va avea valori naturale cuprinse intre
0
si9
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)