257
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; }
Comentarii