fbpx

Problema #3220 – foto – Rezolvari PBInfo

de Mihai-Alexandru

Alina este pasionată de fotografiile alb-negru. Ea ales o imagine pe care a codificat-o binar într-o matrice de dimensiune n x m cu valori 0 corespunzătoare pentru alb (pe care le-a numit puncte luminoase) și cu valori 1 corespunzătoare pentru negru (pe care le-a numit puncte întunecate). Astfel, ea identifică în imaginea codificată zone luminoase și zone întunecate, o zonă fiind o porțiune a matricei care conține elemente cu aceeași valoare, trecerea de la un element la altul al zonei făcându-se doar prin deplasări pe orizontală sau pe verticală.

Cerința

Ajutați-o pe Alina să găsească cea mai luminoasă zonă și determinați numărul de puncte luminoase ale acesteia.

Date de intrare

Pe prima linie a fișierului text foto.in se găsesc două numere naturale n și m care reprezintă numărul liniilor, respectiv numărul coloanelor matricei. Pe următoarele n linii se găsesc câte m valori binare, separate prin câte un spațiu, reprezentând elementele matricei care codifică imaginea.

Date de ieșire

Fișierul de ieșire foto.out trebuie să conțină o singură linie pe care se va afla numărul punctelor din cea mai luminoasă zonă a imaginii.

Restricții și precizări

  • 1 ≤ n ≤ 100, 1 ≤ m ≤ 100, numere naturale
  • dacă nu există nicio zonă luminoasă, se va considera că cea mai luminoasă zonă are 0 elemente

Exemplu

foto.in

6 6
1 0 0 1 1 1
1 1 0 1 0 1
1 0 0 1 0 0
1 1 1 0 1 1
1 0 0 1 1 0
1 0 0 1 1 1

foto.out

5

Explicație

Zona cea mai luminoasă este formată din elementele: (1,2), (1,3), (2,3), (3,2), (3,3).

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

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

int n, m, a[101][101], cnt;
int di[]={0,0,-1,1};
int dj[]={-1,1,0,0};

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

void fill(int i, int j){
    cnt++;
    a[i][j] = 1;
    for(int d = 0; d <= 3; ++d){
        int ii = i + di[d];
        int jj = j + dj[d];
        if(inmat(ii, jj) && a[ii][jj] == 0)
            fill(ii, jj);
    }
}

int main(){
    int max = 0;
    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] == 0){
                cnt=0;
                fill(i, j);
                if(cnt > max)
                    max = cnt;
            }
    cout << max;
    return 0;
}
Comentarii

S-ar putea sa iti placa