Cod sursa(job #1345834)

Utilizator andrettiAndretti Naiden andretti Data 17 februarie 2015 21:39:46
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include<stdio.h>
#include<algorithm>
#define maxn 55
using namespace std;

int T,n,m;
char a[maxn][maxn];
int s[maxn][maxn],c[10],line[10];
long long sol;

void read()
{
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s\n",a[i]+1);
}

void preproc()
{
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
         s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
         if(a[i][j]=='1') s[i][j]++;
     }
}

int get(int x1,int y1,int x2,int y2)
{
    if(x1>x2 || y1>y2) return 0;
    return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}

void solve()
{
    sol=0;
    long long sum,nope,cnt,nr;
    int ok;

    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
      for(int k=i;k<=n;k++)
       for(int l=j;l<=m;l++)
        if(i==k && j==l){
            if(a[i][j]=='1') sol++;
       }
       else
        if(i==k){
            if(a[i][j]!='1' || a[k][l]!='1') continue;
            sol+= (1LL<<get(i,j+1,k,l-1))*(l-j+1);
        }
        else
        if(j==l){
            if(a[i][j]!='1' || a[k][l]!='1') continue;
            sol+= (1LL<<get(i+1,j,k-1,l))*(k-i+1);
        }
       else
       {
           ok=1;
           c[1]=a[i][j]-'0'; c[2]=a[i][l]-'0';
           c[3]=a[k][j]-'0'; c[4]=a[k][l]-'0';
           c[0]=c[4]; c[5]=c[0];

           line[1]=get(i,j,i,l); line[2]=get(i,l,k,l);
           line[3]=get(k,j,k,l); line[4]=get(i,j,k,j);
           line[0]=line[4]; line[5]=line[0];

           for(int it=1;it<=4;it++) if(!line[it]) ok=0;
           if(!ok) continue;


           sum=nope=0;
           for(int it=1;it<=4;it++) sum+=line[it],sum-=c[it];



           for(int mask=1;mask<=15;mask++)
           {
               nr=0; cnt=0;
               for(int it=1;it<=4;it++)
                if( (mask>>(it-1))&1 )
                {
                    nr++;
                    cnt+=line[it];
                    if( it>1 && ((mask>>(it-2))&1) ) cnt-=c[it];
                }

               if( (mask&1) && ((mask>>3)&1) ) cnt-=c[1];

               cnt=sum-cnt;
               if(nr%2==1) nope+= 1LL<<cnt;
               else nope-= 1LL<<cnt;
           }

           sum=(1LL<<sum)-nope;
           sol+= (sum*(1LL<<get(i+1,j+1,k-1,l-1)))*(k-i+1)*(l-j+1);
       }

       for(nr=s[n][m];nr && sol%2==0;sol/=2,nr--);
       printf("%lld/%lld\n",sol,1LL<<nr);
}

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

    for(scanf("%d",&T);T;T--)
    {
        read();
        preproc();
        solve();
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}