Cod sursa(job #1230783)

Utilizator george_stelianChichirim George george_stelian Data 19 septembrie 2014 11:25:36
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.19 kb
#include <cstdio>

using namespace std;

int v1[5000],v2[5000],t,n,m,i,j,q,x,lim,s,nr,maxx,maxy,minx,miny;
char v[5000];

int main()
{
    freopen("boundingbox.in", "r", stdin);
    freopen("boundingbox.out", "w", stdout);
    for(scanf("%d",&t);t;t--)
    {
        scanf("%d%d\n",&n,&m);
        nr=0;
        for(i=1;i<=n;i++)
        {
            scanf("%s\n",v);
            for(j=0;j<m;j++)
                if(v[j]=='1')
                {
                    v1[++nr]=i;
                    v2[nr]=j+1;
                }
        }
        lim=(1<<nr)-1;
        s=0;
        for(i=1;i<=lim;i++)
        {
            maxx=maxy=0;
            minx=miny=50;
            for(j=1,q=1;q<=i;j++,q<<=1)
                if(i&q)
                {
                    if(maxx<v1[j]) maxx=v1[j];
                    if(maxy<v2[j]) maxy=v2[j];
                    if(minx>v1[j]) minx=v1[j];
                    if(miny>v2[j]) miny=v2[j];
                }
            s+=(maxx-minx+1)*(maxy-miny+1);
        }
        lim++;
        while(s%2==0 && lim%2==0)
        {
            s/=2;
            lim/=2;
        }
        printf("%d/%d\n",s,lim);
    }
    return 0;
}