Cod sursa(job #2430433)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 14 iunie 2019 20:27:17
Problema Boundingbox Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.19 kb
#include<fstream>
using namespace std;
ifstream fi("boundingbox.in");
ofstream fo("boundingbox.out");
int n,m,T,t,i,j,ii,jj,A[55][55];
long long mod,a,b,d;
char S[55];

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

int sum(int x, int y, int xx, int yy)
{
    return A[xx][yy]-A[x-1][yy]-A[xx][y-1]+A[x-1][y-1];
}

long long calc(int x, int y, int xx, int yy)
{
    if(x==xx && y==yy)
        return (sum(x,y,xx,yy)==1);
    if(x==xx || y==yy)
    {
        if(sum(x,y,x,y)!=1 || sum(xx,yy,xx,yy)!=1)
            return 0;
        if(x==xx)
            return (1LL<<sum(x,y+1,xx,yy-1));
        return (1LL<<sum(x+1,y,xx-1,yy));
    }
    long long nr1,nr2,nr3,nr4,nr;
    long long rez=0LL;
    int c1=sum(x,y,x,y);
    int c2=sum(xx,y,xx,y);
    int c3=sum(xx,yy,xx,yy);
    int c4=sum(x,yy,x,yy);
    //0
    nr1=sum(x+1,y,xx-1,y);
    nr2=sum(xx,y+1,xx,yy-1);
    nr3=sum(x+1,yy,xx-1,yy);
    nr4=sum(x,y+1,x,yy-1);
    nr=sum(x+1,y+1,xx-1,yy-1);
    rez=(1LL<<nr)*((1LL<<nr1)-1)*((1LL<<nr2)-1)*((1LL<<nr3)-1)*((1LL<<nr4)-1);
    //1
    if(c1==1)
        rez+=(((1LL<<nr3)-1)*((1LL<<nr2)-1)*(1LL<<(nr1+nr4+nr)));
    if(c2==1)
        rez+=(((1LL<<nr3)-1)*((1LL<<nr4)-1)*(1LL<<(nr1+nr2+nr)));
    if(c3==1)
        rez+=(((1LL<<nr1)-1)*((1LL<<nr4)-1)*(1LL<<(nr3+nr2+nr)));
    if(c4==1)
        rez+=(((1LL<<nr3)-1)*((1LL<<nr4)-1)*(1LL<<(nr1+nr2+nr)));
    //2
    if(c1==1 && c3==1)
        rez=rez+(1LL<<(nr+nr1+nr2+nr3+nr4));
    if(c2==1 && c4==1)
        rez=rez+(1LL<<(nr+nr1+nr2+nr3+nr4));
    if(c1==1 && c2==1)
        rez=rez+(1LL<<(nr+nr1+nr2+nr4))*((1LL<<nr3)-1);
    if(c2==1 && c3==1)
        rez=rez+(1LL<<(nr+nr1+nr2+nr3))*((1LL<<nr4)-1);
    if(c3==1 && c4==1)
        rez=rez+(1LL<<(nr+nr4+nr2+nr3))*((1LL<<nr1)-1);
    if(c4==1 && c1==1)
        rez=rez+(1LL<<(nr+nr4+nr1+nr3))*((1LL<<nr2)-1);
    //3
    if(c1==1 && c2==1 && c3==1)
        rez=rez+(1LL<<(nr+nr1+nr2+nr3+nr4));
    if(c1==1 && c2==1 && c4==1)
        rez=rez+(1LL<<(nr+nr1+nr2+nr3+nr4));
    if(c1==1 && c3==1 && c4==1)
        rez=rez+(1LL<<(nr+nr1+nr2+nr3+nr4));
    if(c2==1 && c3==1 && c4==1)
        rez=rez+(1LL<<(nr+nr1+nr2+nr3+nr4));
    //4
    if(c1==1 && c2==1 && c3==1 && c4==1)
        rez=rez+(1LL<<(nr+nr1+nr2+nr3+nr4));
    return rez;
}

int main()
{
    fi>>T;
	for(t=1; t<=T; t++)
	{
        fi>>n>>m;
        for(i=1; i<=n; i++)
        {
            fi>>S;
            for(j=1; j<=m; j++)
            {
                A[i][j]=S[j-1]-'0';
                A[i][j]=A[i][j]+A[i-1][j]+A[i][j-1]-A[i-1][j-1];
            }
        }
        a=0;
        b=1;
        for(i=1; i<=n; i++)
            for(j=1; j<=m; j++)
                for(ii=i; ii<=n; ii++)
                    for(jj=j; jj<=m; jj++)
                    {
                        mod=calc(i,j,ii,jj);
                        a=a+1LL*mod*(ii-i+1)*(jj-j+1);
                        b=b+mod;
                    }
        d=gcd(a,b);
        a/=d;
        b/=d;
        fo<<a<<"/"<<b<<"\n";
	}
	fi.close();
    fo.close();
    return 0;
}