Cod sursa(job #1230832)

Utilizator atatomirTatomir Alex atatomir Data 19 septembrie 2014 12:05:10
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.8 kb
#include <iostream>
#include <cstdio>

using namespace std;

#define maxComb 50
#define x first
#define y second

long t,ti,n,m,i,j;
long cont;
long long ansA,ansB;
char s[maxComb+10];
pair<long,long> pts[maxComb+10];
long long c[maxComb+10][maxComb+10];
long long cmm;

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;
}


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];
    }
}

void Recurs(long pas,long minI,long maxI,long minJ,long maxJ,bool sel){
    if(pas > cont){
        if(!sel) return;
        ansA  = ansA + 1LL*(maxI-minI+1)*(maxJ-minJ+1);
        return;
    }

    Recurs(pas+1,minI,maxI,minJ,maxJ,sel);
    minI = min(minI,pts[pas].x);
    minJ = min(minJ,pts[pas].y);
    maxI = max(maxI,pts[pas].x);
    maxJ = max(maxJ,pts[pas].y);
    Recurs(pas+1,minI,maxI,minJ,maxJ,true);
}

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

    preCalculate();

    scanf("%ld",&t);
    for(ti=1;ti<=t;ti++){
        scanf("%ld %ld\n",&n,&m);
        cont = 0;

        for(i=1;i<=n;i++){
            scanf("%s\n",s+1);
            for(j=1;j<=m;j++){
                if(s[j] == '1') pts[++cont].first = i,pts[cont].second = j;
            }
        }

        ansA = 0; ansB = (cont != n*m?1:0);
        for(i=1;i<=cont;i++)
            ansB = ansB + c[cont][i];

        Recurs(1,51,0,51,0,false);


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

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

    }


    return 0;
}