Cod sursa(job #1230742)

Utilizator atatomirTatomir Alex atatomir Data 19 septembrie 2014 10:49:18
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 2.02 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define maxComb 50

long t,i,j,i2,j2,ti;
long long a,b,c[maxComb+10][maxComb+10];
long n,m,sum[maxComb][maxComb];
char s[maxComb];

long long ansA,ansB,cmm;
long cont;

void preCalculate() {
    c[0][0] = 1;
    for(long i=1;i<=maxComb;i++){
        c[i][0] = 1;
        for(long j=1;j<=i;j++) c[i][j] = c[i-1][j-1] + c[i-1][j];
    }

}

inline bool exist(long i,long j,long i2,long j2){
    if(sum[i2][j2] - sum[i-1][j2] - sum[i2][j-1] + sum[i-1][j-1]) return true;
    return false;
}

bool valid(long i,long j,long i2,long j2){
    if(exist(i,j,i,j2))
        if(exist(i2,j,i2,j2))
            if(exist(i,j,i2,j))
                if(exist(i,j2,i2,j2))
                    return true;
    return false;
}

long long cmmdc(long long a,long long b){
    long long t;
    if(a < b) {t=a;a=b;b=t;}
    while(b){
        a = a%b;
        t=a;a=b;b=t;
    }
    return a;
}

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

    preCalculate();

    scanf("%ld",&t);
    for(ti=1;ti<=t;ti++){
        memset(sum,0,sizeof(sum));
        cont = 0;

        scanf("%ld %ld\n",&n,&m);
        for(i=1;i<=n;i++){
            scanf("%s\n",s);
            for(j=1;j<=m;j++){
                if(s[j-1] == '1') sum[i][j] = 1,cont++;
                sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            }
        }

        ansA = 0; ansB = 1;

        for(i=1;i<=cont;i++) ansB = ansB + c[cont][i];

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                for(i2=i;i2<=n;i2++)
                    for(j2=j;j2<=m;j2++){
                        if(valid(i,j,i2,j2))
                            ansA = ansA + 1LL*((i2-i+1)*(j2-j+1));
                    }

        cmm = cmmdc(ansA,ansB);
        ansA = ansA / cmm;
        ansB = ansB / cmm;

        printf("%lld/",ansA);
        printf("%lld\n",ansB);
    }

    return 0;
}