Cod sursa(job #1230988)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 19 septembrie 2014 13:55:20
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 3.39 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,conf;
int wh[20];
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 < 3 ? x+1 : 0;
}

inline long long give (int conf)
{
    return (pw[d[1]]-(conf&1)) * (pw[d[2]]-((conf>>1)&1)) * (pw[d[3]] - ((conf>>2)&1)) * (pw[d[4]]-((conf>>3)&1));
}

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

    if (p == 5)
    {
        return give(wh[conf]);
    }

    if (b[p] == 1)
    {
        conf += (1<<(p-1));
        s = back(p+1);
        conf -= (1<<(p-1));
        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;

     for (int i=0; i<16; ++i)
     {
         for (int k=0; k<4; ++k)
         {
             take[k] = ((i>>k)&1);
         }

         for (int k=0; k<4; ++k)
         {
             if (!take[k] && !take[next(k)])
             {
                 wh[i] += (1<<k);
             }
         }
     }

    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";
    }
}