Cod sursa(job #1230818)

Utilizator andrettiAndretti Naiden andretti Data 19 septembrie 2014 11:49:57
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.25 kb
#include<stdio.h>
#include<algorithm>
#define maxn 55
using namespace std;

int T,n,m,nr;
char a[maxn][maxn];
int s[maxn][maxn];
int Area;

void read()
{
    scanf("%d%d\n",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s\n",a[i]+1);
}

void preproc()
{
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]-'0';
}

int sum(int i,int j,int k,int l){
    return s[k][l]-s[i-1][l]-s[k][j-1]+s[i-1][j-1];
}

int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}

void solve()
{
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      for(int k=i;k<=n;k++)
       for(int l=j;l<=m;l++)
       {
           if(sum(i,j,i,l)>0 && sum(k,j,k,l)>0 && sum(i,j,k,j)>0 && sum(i,l,k,l)>0)
           {
               nr++;
               Area+=(k-i+1)*(l-j+1);
           }
       }
    nr++;
    int d=gcd(Area,nr);
    Area/=d; nr/=d;
}

int main()
{
    freopen("boundingbox.in","r",stdin);
    freopen("boundingbox.out","w",stdout);

    scanf("%d",&T);
    for(;T;T--)
    {
        Area=0; nr=0;
        read();
        preproc();
        solve();
        printf("%d/%d\n",Area,nr);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}