Cod sursa(job #1230943)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 19 septembrie 2014 13:23:13
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 3.07 kb
#include <fstream>

#define maxn 55

using namespace std;

ifstream fin ("boundingbox.in");
ofstream fout ("boundingbox.out");

int a[maxn][maxn];
char s[maxn][maxn];
int b[10],d[10],r,c,take[10],test;
long long ans,pw[maxn];

int sub (int i, int j, int k, int h)
{
    if (i > j || k > h)
      return 0;
    return a[j][h] - a[i-1][h] - a[j][k-1] + a[i-1][k-1];
}

inline int next (int x)
{
    return x < 4 ? x+1 : 1;
}

long long back (int p)
{
    long long s = 1;

    if (p == 5)
    {
        for (int i=1; i<=4; ++i)
        {
            if (!take[i] && !take[next(i)])
            {
                s *= pw[d[i]]-1;
            }
            else s *= pw[d[i]];
        }

        return s;
    }

    if (b[p] == 1)
    {
        take[p] = 1;
        s = back(p+1);
        take[p] = 0;
        s += back(p+1);
    }
    else s = back (p+1);

    return s;
}

long long cmmdc (long long a, long long b)
{
    if (b == 0) return a;
    return cmmdc (b,a%b);
}

int main()
{
    pw[0] = 1;
    for (int i=1; i<=50; ++i)
     pw[i] = pw[i-1]*2;

    fin>>test;

    for (;test; --test)
    {
        fin>>r>>c;

        for (int i=1; i<=r ; ++i)
            fin>>s[i]+1;

        for (int i=1; i<=r; ++i)
        {
            for (int j=1; j<=c; ++j)
            {
                a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + (s[i][j]-'0');
            }
        }

        ans = 0;

        for (int i=1; i <= r; ++i)
        {
            for (int j=i; j<=r; ++j)
            {
                for (int k=1; k<=c; ++k)
                {
                    for (int h=k; h <= c; ++h)
                    {
                        if (j == i && k == h)
                         {
                           if (s[i][k] == '1')
                           ans += 1;
                         }
                        else if (j == i)
                         {
                             if (s[i][k] == '1' && s[i][h] == '1')
                             ans += (h-k+1)*(pw[sub(i,j,k,h)-2]);
                        }
                        else if (k == h)
                         {
                             if  (s[i][k] == '1' && s[j][k] == '1')
                            ans += (j-i+1)*(pw[sub(i,j,k,h)-2]);
                         }
                        else
                        {
                            b[1] = s[i][k]-'0';
                            b[2] = s[i][h]-'0';
                            b[3] = s[j][h]-'0';
                            b[4] = s[j][k]-'0';

                            d[1] = sub (i,i,k+1,h-1);
                            d[2] = sub (i+1,j-1,h,h);
                            d[3] = sub (j,j,k+1,h-1);
                            d[4] = sub (i+1,j-1,k,k);

                            ans += back (1)*(j-i+1)*(h-k+1)*pw[sub(i+1,j-1,k+1,h-1)];
                        }
                    }
                }
            }
        }

        long long num = pw[a[r][c]];

        fout<<ans/cmmdc(ans,num)<<"/"<<num/cmmdc(ans,num)<<"\n";
    }
}