Cerința

Se dă o matrice reprezentând o zonă dintr-un ocean ce conține un iceberg; valorile egale cu 1 fac parte din iceberg, iar cele egale cu 0 reprezintă apă.

Se știe că icebergul este înconjurat de apa (nu există nici o valoare de 1 pe marginea matricei) și că într-un interval de timp se topesc toate zonele icebergului care au cel puțin doua laturi vecine cu apa.

Determinați și afișați cate intervale de timp sunt necesare ca icebergul să se topească în întregime. De asemenea, afișați pentru fiecare interval de timp câte poziții de gheață are icebergul la începutul intervalului.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi o matrice de n linii și n coloane reprezentând zona icebergului.

Date de ieșire

Programul va afișa pe ecran numărul t reprezentând numărul de intervale de timp și t numere naturale reprezentând suprafața ghețarului la începutul fiecărui interval.

Restricții și precizări

• 1 ≤ n ≤ 31
• Elementele de pe marginile matricii sunt tot timpul 0

Exemplu

Intrare

7
0 0 0 0 0 0 0 
0 1 1 1 1 1 0 
0 0 1 1 1 0 0 
0 0 1 1 1 0 0 
0 1 1 1 1 1 0 
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Ieșire

4
16
12
8
2

Explicație

După primul interval de timp ghețarul arată astfel:

0 0 0 0 0 0 0 
0 0 1 1 1 0 0 
0 0 1 1 1 0 0 
0 0 1 1 1 0 0 
0 0 1 1 1 0 0 
0 0 0 0 0 0 0 

După cel de-al doilea interval de timp ghețarul arată astfel:

0 0 0 0 0 0 0 
0 0 0 1 0 0 0 
0 0 1 1 1 0 0 
0 0 1 1 1 0 0 
0 0 0 1 0 0 0 
0 0 0 0 0 0 0 

După cel de-al treilea interval de timp ghețarul arată astfel:

0 0 0 0 0 0 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 0 
0 0 0 1 0 0 0 
0 0 0 0 0 0 0 
0 0 0 0 0 0 0 

iar la pasul următor se topește de în întregime.

#include <bits/stdc++.h>
using namespace std;
bool a[102][102] , b[102][102];
int main()
{
    int n , cnt = -1 , ok = 0 , v[101] , p = 0 , s = 0 , suma = 0;
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        a[i][0]=1;
        a[i][n+1]=1;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        a[0][i]=1;
        a[n+1][i]=1;
    }
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
        {
            cin >> a[i][j];
            b[i][j]=a[i][j];
            if(a[i][j]==1) s++;
        }
    suma = s;
    v[p]=s , p++;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            if(a[i][j]==1) ok = 1;
    while(ok == 1)
    {
        int r = 0;
        ok = 0;
        cnt++;
        for(int i = 1 ; i <= n ; ++i)
            for(int j = 1 ; j <= n ; ++j)
                if((a[i+1][j]==0 && a[i][j+1]==0)||(a[i+1][j]==0 && a[i-1][j]==0)||(a[i+1][j]==0 && a[i][j-1]==0)||(a[i][j+1]==0 && a[i-1][j]==0)||(a[i][j+1]==0 && a[i][j-1]==0)||(a[i-1][j]==0 && a[i][j-1]==0))
                    b[i][j]=0;
        for(int i = 1 ; i <= n ; ++i)
            for(int j = 1 ; j <= n ; ++j)
                if(b[i][j]!=a[i][j]) ok = 1 , r++;
        for(int i = 1 ; i <= n ; ++i)
            for(int j = 1 ; j <= n ; ++j)
                a[i][j]=b[i][j];
        suma = suma - r;
        v[p]=suma , p++;
    }
    ok = 0;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            if(a[i][j]==1) ok=1;
    if(ok==0) cout << cnt;
    else cout << -1;
    cout << endl;
    for(int i = 0 ; i < p ; ++i) if(v[i]!=0)cout << v[i] << endl;
    return 0;
}