Cod sursa(job #1230858)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 19 septembrie 2014 12:23:15
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 3.13 kb
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>

using namespace std;

#define maxn 55

int n, m;
int v[maxn][maxn], sum[maxn][maxn];
long long fav, tot;
string s;

int count(int x1, int y1, int x2, int y2)
{
    if(x2<x1 || y2<y1)
        return 0;
    return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}

long long marked(int um, int dm, int lm, int rm, int u, int d, int l, int r)
{
    long long rez = 1;

    if(um==1)
        rez = rez * (1LL<<u);
    else
        rez = rez * ((1LL<<u) - 1);

    if(dm==1)
        rez = rez * (1LL<<d);
    else
        rez = rez * ((1LL<<d) - 1);

    if(lm==1)
        rez = rez * (1LL<<l);
    else
        rez = rez * ((1LL<<l) - 1);

    if(rm==1)
        rez = rez * (1LL<<r);
    else
        rez = rez * ((1LL<<r) - 1);
}


long long rez(int a, int b, int c, int d)
{
    int aria = (c-a+1)*(d-b+1);

    int U = count(a, b+1, a, d-1);
    int D = count(c, b+1, c, d-1);
    int L = count(a+1, b, c-1, b);
    int R = count(a+1, d, c-1, d);

    long long cr = 0;

    for(int ul = 0; ul < 2; ++ul)
    {
        if(ul==1 && v[a][b]==0)
            continue;

        for(int ur = 0; ur < 2; ++ur)
        {
            if(ur==1 && v[a][d]==0)
                continue;

            for(int dl = 0; dl < 2; ++dl)
            {
                if(dl==1 && v[c][b]==0)
                    continue;

                for(int dr = 0; dr < 2; ++dr)
                {
                    if(dr==1 && v[c][d]==0)
                        continue;

                    cr += marked(ul|ur, dl|dr, ul|dl, ur|dr, U, D, L, R);
                }
            }
        }
    }

    cr = cr * aria * (1LL<<count(a+1, b+1, c-1, d-1));

    return cr;
}

long long cmmdc(long long a, long long b)
{
    long long r=a%b;

    while(r>0)
    {
        a=b;
        b=r;
        r=a%b;
    }

    return b;
}


void solve()
{
    memset(v, 0, sizeof(v));
    memset(sum, 0, sizeof(sum));

    cin>>n>>m;

    for(int i=1; i<=n; ++i)
    {
        cin>>s;
        for(int j=0; j<m; ++j)
        {
            v[i][j+1]=s[j]-'0';
            sum[i][j+1]=sum[i][j]+v[i][j+1];
        }
    }

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            sum[i][j]+=sum[i-1][j];

    int total = sum[n][m];

    fav = 0;
    tot = (1LL<<total);

    for(int a=1; a<=n; ++a)
        for(int c=a+1; c<=n; ++c)
            for(int b=1; b<=m; ++b)
                for(int d=b+1; d<=m; ++d)
                    fav += rez(a, b, c, d);

    for(int a=1; a<=n; ++a)
        for(int c=a+1; c<=n; ++c)
            for(int b=1; b<=m; ++b)
                if(v[a][b]==1 && v[c][b]==1)
                    fav += (c-a+1) * (1LL<<count(a+1, b, c-1, b));

     for(int b=1; b<=m; ++b)
        for(int d=b+1; d<=m; ++d)
            for(int a=1; a<=n; ++a)
                if(v[a][b]==1 && v[a][d]==1)
                    fav += (d-b+1) * (1LL<<count(a, b+1, a, d-1));

    fav += sum[n][m];

    long long x = cmmdc(fav, tot);

    printf("%lld/%lld\n", fav/x, tot/x);
}

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

    int t;

    cin>>t;
    while(t--)
        solve();

    return 0;
}