Cerința

Se consideră o matrice cu n linii și m coloane. Spunem că o poziție este liberă dacă elementul de pe linia i și coloana j este egal cu 0 și 1 în caz contrar. Spunem despre mai multe elemente ocupate că formează o zonă, dacă elementele se învecinează pe cele patru direcții (sus, jos, dreapta, stânga).

Calculați pentru fiecare zonă numărul de elemente și afișați noua matrice formată prin înlocuirea elementelor egale cu 1 cu numărul de elemente pe care îl are zona din care face parte elementul respectiv.

Date de intrare

De pe prima linie a fișierului zona3.in se citesc două numere naturale n și m. Următoarele n linii conțin câte m valori 0 sau 1.

Date de ieșire

Scrieți în fișierul zona3.out matricea care rezultă din operațiile specificate în cerință.

Restricții și precizări

• 2 ≤ n, m ≤ 100

Exemplu

zona3.in

6 8
1 1 0 0 1 1 1 0
0 0 0 1 1 1 0 0
1 1 0 0 0 1 0 0
0 1 1 1 1 0 0 0
0 0 0 0 1 1 0 0
1 1 0 1 0 0 0 1

zona3.out

2 2 0 0 7 7 7 0
0 0 0 7 7 7 0 0
8 8 0 0 0 7 0 0
0 8 8 8 8 0 0 0
0 0 0 0 8 8 0 0
2 2 0 1 0 0 0 1

Explicație

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

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

int a[105][105] , b[105][105] , v[10005] , p = 1;

void fill(int i , int j , int &c)
{
    if(a[i][j]==1)
    {
        a[i][j]=0;
        c++;
        if(a[i+1][j]==1)
            fill(i+1 , j , c);
        if(a[i-1][j]==1)
            fill(i-1 , j , c);
        if(a[i][j+1]==1)
            fill(i , j+1 , c);
        if(a[i][j-1]==1)
            fill(i , j-1 , c);
    }
}

void fill1(int i , int j , int val)
{
    if(b[i][j]==1)
    {
        b[i][j]=val;
        if(b[i+1][j]==1)
            fill1(i+1 , j , val);
        if(b[i-1][j]==1)
            fill1(i-1 , j , val);
        if(b[i][j+1]==1)
            fill1(i , j+1 , val);
        if(b[i][j-1]==1)
            fill1(i , j-1 , val);
    }
}

int main()
{
    int n , m;
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            cin >> a[i][j] , b[i][j] = a[i][j];
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(a[i][j]==1)
            {
                int c = 0;
                fill(i , j , c);
                v[p]=c;
                p++;
            }
    p--;
    int cnt=1;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(b[i][j]==1)
            {
                fill1(i , j , v[cnt]);
                cnt++;
            }
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= m ; ++j)
            cout << b[i][j] << ' ';
        cout << endl;
    }
    return 0;
}