Cod sursa(job #1230911)

Utilizator geniucosOncescu Costin geniucos Data 19 septembrie 2014 13:00:30
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 3.53 kb
#include<cstdio>
using namespace std;

int arie, T, i, j, n, m, s[59][59];
long long ToT, A, B, C, tot;
char mat[59][59];

int suma(int i1,int j1,int i2,int j2)
{
    if (i1>i2||j1>j2) return 0;
    return  s[i2][j2]-s[i1-1][j2]-s[i2][j1-1]+s[i1-1][j1-1];
}

long long macar(int n, bool v)
{
    if (v==0) return ((long long)(1LL<<n)-1);
    return (1LL<<n);
}

long long gcd(long long a,long long b)
{
    long long r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main()
{
freopen ("boundingbox.in", "r", stdin);
freopen ("boundingbox.out", "w", stdout);
scanf ("%d", &T);
while (T)
{
    T--;
    scanf ("%d %d\n", &n, &m);
    for (int i=1; i<=n; i++)
        gets (mat[i] + 1);
    for (int i=1; i<=n;i++)
        for (int j=1;j<=m; j++)
        {
            mat[i][j]-='0';
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+mat[i][j];
        }
    B = (1LL<<s[n][m]);
    ToT = 0;
    for (int i1 = 1; i1<=n ;i1++)
        for (int j1=1; j1<=m ;j1++)
            for (int i2=i1; i2<=n; i2++)
                for (int j2=j1; j2<=m; j2++)
                {
                    long long tot=0;
                    if (i1==i2 && j1==j2)
                    {
                        ToT+=mat[i1][j1];
                        continue;
                    }
                    if (i1==i2)
                    {
                        if(mat[i1][j1]&&mat[i1][j2])
                            tot = 1LL*(j2-j1+1)*(1LL<<suma(i1,j1+1,i1,j2-1));
                    }
                    if (j1==j2)
                    {
                        if(mat[i1][j1]&&mat[i2][j1])
                            tot = 1LL*(i2-i1+1)*(1LL<<suma(i1+1,j1,i2-1,j1));
                    }
                    if (i1==i2||j1==j2)
                    {
                        ToT+=tot;
                        continue;
                    }
                    arie = suma(i1,j1,i2,j2);
                    int sus, jos, st, dr;
                    sus=jos=st=dr=0;
                    sus = suma(i1,j1,i1,j2);
                    jos = suma(i2,j1,i2,j2);
                    st = suma(i1,j1,i2,j1);
                    dr = suma(i1,j2,i2,j2);
                    if (sus*jos *st*dr == 0) continue;
                    if (mat[i1][j1]) sus--, st--, arie--;
                    if (mat[i2][j1]) st--, jos--, arie--;
                    if (mat[i1][j2]) sus--, dr--, arie--;
                    if (mat[i2][j2]) jos--, dr--, arie--;
                    arie -= sus;
                    arie -= jos;
                    arie -= st;
                    arie -= dr;

                    int Sa=0;
                    if (mat[i1][j1]) Sa|=1;
                    if (mat[i1][j2]) Sa|=2;
                    if (mat[i2][j1]) Sa|=4;
                    if (mat[i2][j2]) Sa|=8;
                    for (int msk = 0; msk < 16; msk++)
                    if ((msk&Sa)==msk)
                    {
                        bool m1, m2, m3, m4;
                        m1=m2=m3=m4=0;
                        if (msk&1) m1=m4=1;
                        if (msk&2) m1=m2=1;
                        if (msk&4) m3=m4=1;
                        if (msk&8) m3=m2=1;
                        tot+=1LL*macar(sus,m1)*macar(st,m4)*macar(dr,m2)*macar(jos,m3);
                    }
                    tot = 1LL*tot*(i2-i1+1)*(j2-j1+1)*(1LL<<arie);
                    ToT+=tot;
                }
    A = ToT;
    C = gcd(A,B);
    printf ("%lld/", A/C);
    printf("%lld\n", B/C);
}
return 0;
}