Cod sursa(job #1230767)

Utilizator akaprosAna Kapros akapros Data 19 septembrie 2014 11:16:40
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.35 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,j,p,q,nr,t,m,k,cm,cM,lm,lM,ok;
int d[55][55];
char a[55][55];
int w[55];
int s;
struct nod
{
    int x;
    int y;
}v[55];
int main()
{
    freopen("boundingbox.in","r",stdin);
    freopen("boundingbox.out","w",stdout);
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d %d\n",&n,&m);
        p=0;
        for (i=1;i<=n;i++)
        {
            gets(a[i]+1);
            for (j=1;j<=m;j++)
            if (a[i][j]=='1') v[++p].x=i,v[p].y=j;
        }
        s=p+1;
        for (i=1;i<p;i++) for (j=i+1;j<=p;j++)
        d[i][j]=d[j][i]=abs(v[i].x-v[j].x)*abs(v[i].y-v[j].y),s=s+d[i][j];
        k=1<<p; s=s+(k/2); q=1<<p;
        nr=1; s=0;
        if (t==6)
        i=i;
        while (nr<=q)
        {
            w[0]=0; cm=55; lm=55; cM=0; lM=0; k=nr; ok=0;
            while (k)
            {
                w[++w[0]]=k%2;
                k=k/2;
            }
            for (i=1;i<=p;i++) if ((w[i]==1)&&(i<=w[0]))
            lm=min(lm,v[i].x),lM=max(lM,v[i].x),cm=min(cm,v[i].y),cM=max(cM,v[i].y),ok=1;
            if (ok) s=s+(cM-cm+1)*(lM-lm+1);
            nr++;
        }
        int D=0,I=0,R=0;
        D=s; I=q; R=D%I;
        while (R) D=I,I=R,R=D%I;
        printf("%d/%d\n",s/I,q/I);
    }
    return 0;
}