Cerința

Gigel este patronul unui fast-food destul de cunoscut. Restaurantul are formă dreptunghiulară, și conține mai multe mese de formă de asemenea dreptunghiulară dar de dimensiuni neregulate. Gigel vă pune la dispoziție planul restaurantului, sub forma unei matrice cu n linii și m coloane, în care elementele care corespund unor spații libere sunt egale cu 0, iar elementele care fac parte din mese sunt egale cu 1. Mai precis, mesele sunt zone dreptunghiulare maximale din matrice care au toate elementele 1.

Rugămintea lui Gigel este să aflați câte mese sunt în local și care este suprafața maximă unei mese.

Date de intrare

Programul citește de la tastatură numerele n m, iar apoi n*m numere naturale (0 sau 1), dispuse pe n ,linii, reprezentând planul restaurantului.

Date de ieșire

Programul va afișa pe ecran numerele C M, separate prin exact un spațiu reprezentând numărul total de mese și suprafața maximă a unei mese.

Restricții și precizări

• 1 ≤ n, m ≤ 250
• mesele nu au laturi comune
• nici o masă nu va conține spații libere
• suprafața unei mese este egală cu numărul de elemente din matrice din care este alcătuită

Exemplu

Intrare

5 6
0 0 1 1 1 0
0 0 1 1 1 0
1 0 0 0 0 1
1 0 1 1 0 1
1 0 1 1 0 0

Ieșire

4 6

#include <bits/stdc++.h>
using namespace std;
const int di[]={-1 , 0 , 1 , 0};
const int dj[]={0 , 1 , 0 , -1};
int n , m , a[1002][1002] , x[1000001] , y[1000001];
int ip , jp , is , js;
bool inside(int i , int j)
{
    return i>=1 && i<=n && j>=1 && j<=m;
}
void lee(int ip , int jp)
{
    int st = 1 , dr = 1;
    a[ip][jp] = 2;
    x[1]=ip;
    y[1]=jp;
    while(st <= dr)
    {
        int i= x[st] , j = y[st];
        for(int k = 0 ; k < 4 ; k++)
        {
            int ii = i+di[k];
            int jj = j+dj[k];
            if(inside(ii , jj) && a[ii][jj]==1)
            {
                dr++;
                x[dr]=ii;
                y[dr]=jj;
                a[ii][jj]=2;
            }}st++;}
}
int main()
{
    int p = 0 , k = 0 , 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]==1)
            {
                int lat = 0 , col = 0;
                while(a[i][j]==1){lat++;j++;}
                j-=lat;
                while(a[i][j]==1){col++;i++;}
                if(lat * col>max) max=lat*col;
                i-=col;
            }
    for(int i = 1 ; i <=n ; ++i)
    {
        if(a[i][1]==1){p++;lee(i,1);}
        if(a[i][m]==1){p++;lee(i,m);}
    }
    for(int i = 1 ; i <=m ; ++i)
    {
        if(a[1][i]==1){p++;lee(1,i);}
        if(a[n][i]==1){p++;lee(n,i);}
    }
    for(int i = 2 ; i <n ; ++i)
        for(int j = 2 ; j <m ; ++j)
            if(a[i][j]==1)
            {
                k++;
                lee(i,j);
            }
    cout << k+p << " " << max;
    return 0;
}