11/15 - Algoritmul Fill

Fiind data o matrice m x n, unde m,n apartin lui N si exista y elemente notate cu 1 si z elemente notate cu 0 iar y+z=m*n, aflati aria cea mai intinsa de elemente de 1.
Exemplu:
m=4, n=4
matricea:
0 1 1 0
0 1 1 0
1 0 0 0
0 0 1 1
Se va afisa: 4, adica regiunea care cuprinde elementele: (1,2),(1,3),(2,2),(2,3)

#include<fstream>
#include<iostream>
#include<iomanip>
using namespace std;
int a[100][100],n,m;
int size;
void fill(int i,int j,int k)
{
    if(a[i][j]==1)
    {
        a[i][j]=k; // fiecarei element din regiune ii corespunde numarul zonei
        size++;
       /*verificam daca elementele alaturate pot apartine aceiasi regiuni si daca nu au fost 
         inca marcate*/
        fill(i-1,j,k);
        fill(i+1,j,k);
        fill(i,j-1,k);
        fill(i,j+1,k);
    }
}

int main()
{
    int i,j;
    ifstream f("fill.in");
    f>>m>>n;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            f>>a[i][j];
    int max=0;
    int k=1;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]==1){
                k++; //fiecarei regiuni ii va corespunde un numar de ordine
                size=0;//numarul de elemente dintr-o regiune este initial 0
                fill(i,j,k);
                if(max<size) max=size;//calculam maximul ariilor
            }
    cout<<max<<endl;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
            cout<<setw(3)<<a[i][j];
    cout<<endl;
    }return 0;
}

Fisier

4 4
0 1 1 1
0 1 1 1
1 1 1 1
0 0 1 1