Cod sursa(job #1231057)

Utilizator andrettiAndretti Naiden andretti Data 19 septembrie 2014 14:44:31
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 2.75 kb
#include<stdio.h>
#include<algorithm>
#define maxn 55
using namespace std;

int T,n,m;
char a[maxn][maxn];
int s[maxn][maxn],ok[5],l1[maxn],l2[maxn],c1[maxn],c2[maxn];
int lin[5],col[5];
long long Area,nr;

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]+a[i][j]-'0';
}

int sum(int i,int j,int k,int l){
    if(i>k || j>l) return 0;
    return s[k][l]-s[i-1][l]-s[k][j-1]+s[i-1][j-1];
}

void solve()
{
    int nrc;
    int cnt,aux,lim=(1<<4)-1;
    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(sum(i,j,i,l)>0 && sum(i,l,k,l)>0 && sum(k,j,k,l)>0 && sum(i,j,k,j)>0)
       {

           nrc=0;
           l1[1]=i; c1[1]=j+1; l2[1]=i; c2[1]=l-1;
           l1[2]=i+1; c1[2]=l; l2[2]=k-1; c2[2]=l;
           l1[3]=k; c1[3]=j+1; l2[3]=k; c2[3]=l-1;
           l1[4]=i+1; c1[4]=j; l2[4]=k-1; c2[4]=j;

           lin[0]=lin[1]=i; lin[2]=lin[3]=k;
           col[0]=col[3]=j; col[1]=col[2]=l;

           for(int it=0;it<=lim;it++)
           {
               aux=0;
               for(int x=1;x<=4;x++) ok[x]=0;

               for(int x=0;x<=3;x++)
                if( ((it>>x)&1) &&  a[lin[x]][col[x]]=='0') {aux=1; break;}
                else
                {
                    if(x==0) ok[1]=ok[4]=1;
                    else
                     if(x==1) ok[1]=ok[2]=1;
                     else
                      if(x==2) ok[2]=ok[3]=1;
                      else ok[3]=ok[4]=1;
                }
                if(aux==1) continue;

                for(int x=1;x<=4;x++)
                 if(!ok[x] && sum(l1[x],c1[x],l2[x],c2[x])==0) {aux=1; break;}

                if(aux==1) continue;

                cnt=1;
                for(int x=1;x<=4;x++)
                 if(ok[x])
                  cnt=cnt*(1LL<<sum(l1[x],c1[x],l2[x],c2[x]));
                 else
                  cnt=cnt*((1LL<<sum(l1[x],c1[x],l2[x],c2[x]))-1);


                nrc+=cnt;
                //printf("%d %d %d %d ->>%d->>%d\n",i,j,k,l,it,cnt);
           }
           //printf("%d %d %d %d ->>%d\n",i,j,k,l,nrc);

           Area=Area+1LL*nrc*(k-i+1)*(l-j+1);
       }

    nr=1LL<<s[n][m];
    while(Area%2==0 && nr%2==0) Area/=2,nr/=2;
}

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

    scanf("%d",&T);
    for(;T;T--)
    {
        Area=0; nr=0;
        read();
        preproc();
        solve();
        printf("%lld/",Area);
        printf("%lld\n",nr);
    }

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