Cerința

Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, care reprezintă harta unui lac, în care 0 înseamnă uscat, iar 1 înseamnă apă.

Se dorește plasarea pe fiecare zonă cu uscat a unui crocodil sau a unui elefant astfel încât să nu fie două animale din aceeași specie în zone învecinate. În plus, se dorește ca numărul de crocodil să fie cât mai mare.

Să se determine câți crocodili și câți elefanți se pot plasa pe lac, astfel încât numărul de crocodili să fie cât mai mare.

Date de intrare

Fișierul de intrare croco1.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m elemente, 0 sau 1, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire croco1.out va conține pe prima linie numerele C E, reprezentând numărul de crocodili, respectiv numărul de elefanți care pot fi plasați în condițiile precizate, astfel încât numărul de crocodili să fie cât mai mare.

Restricții și precizări

• 1 ≤ n , m ≤ 100

Exemplu

croco1.in

3 5
0 0 0 1 0
0 0 1 0 0
1 0 0 1 0

croco1.out

7 4

Explicație

O posibilitate de plasare a animalelor cu număr maxim de crocodili este următoarea:

C E C A C
E C A C E
A E C A C

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

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

int a[105][105] , n , m , cnt1=0 , cnt2=0;

void fill(int i , int j , bool c)
{
        a[i][j]=1;
        if(c)
            cnt1++;
        else
            cnt2++;
        c=!c;
        if(a[i+1][j]==0 && i+1 <= n)
            fill(i+1 , j , c);
        if(a[i-1][j]==0 && i-1 >= 1)
            fill(i-1 , j , c);
        if(a[i][j+1]==0 && j+1 <= m)
            fill(i , j+1 , c);
        if(a[i][j-1]==0 && j-1 >= 1)
            fill(i , j-1 , c);
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            cin >> a[i][j];
    int croco=0 , ele=0;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            if(a[i][j]==0)
            {
                cnt1=0 , cnt2=0;
                bool c=true;
                fill(i , j , c);
                if(cnt1>cnt2)
                    croco+=cnt1 , ele+=cnt2;
                else
                    croco+=cnt2 , ele+=cnt1;
            }
    cout << croco << ' ' << ele;
    return 0;
}