Cod sursa(job #1479324)

Utilizator ZenusTudor Costin Razvan Zenus Data 31 august 2015 03:03:17
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.9 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 50 + 10;

string cs;
int n , m , teste , ones , area , cover , I0 , I1 , J0 , J1 , i , j , k;
int LU , RU , LD , RD , L , R , U , D , q;
long long xx , yy , rr , ans;
int s[nmax][nmax] , r[nmax][nmax] , c[nmax][nmax] , x[nmax][nmax];

int row(int i , int J0 , int J1)
{
    return r[i][J1] - r[i][J0 - 1];
}

int column(int j , int I0 , int I1)
{
    return c[I1][j] - c[I0 - 1][j];
}

int main()
{

for (fin >> teste ; teste ; --teste)
{
    fin >> n >> m;
    memset(x , 0 , sizeof(x));
    memset(r , 0 , sizeof(r));
    memset(c , 0 , sizeof(c));
    memset(s , 0 , sizeof(s));
    xx = 0;

    for (i = 1 ; i <= n ; ++i)
    {
        fin >> cs;
        for (j = 1 ; j <= m ; ++j)
        x[i][j] = cs[j - 1] - '0';
    }

    for (i = 1 ; i <= n ; ++i)
    for (j = 1 ; j <= m ; ++j)
    r[i][j] = x[i][j] + r[i][j - 1];

    for (i = 1 ; i <= n ; ++i)
    for (j = 1 ; j <= m ; ++j)
    c[i][j] = x[i][j] + c[i - 1][j];

    for (i = 1 ; i <= n ; ++i)
    for (j = 1 ; j <= m ; ++j)
    s[i][j] = x[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    if (s[n][m] == 0)
    {
        fout << "0/1" << '\n';
        continue;
    } else yy = 1LL << s[n][m];

    for (I0 = 1 ; I0 <= n ; ++I0)
    for (J0 = 1 ; J0 <= m ; ++J0)
    for (I1 = I0 ; I1 <= n ; ++I1)
    for (J1 = J0 ; J1 <= m ; ++J1)
    {
        k = s[I1][J1] - s[I1][J0 - 1] - s[I0 - 1][J1] + s[I0 - 1][J0 - 1];
        area = (J1 - J0 + 1) * (I1 - I0 + 1);

        if (k == 0) continue;

        if (I0 == I1 && J0 == J1)
        {
            if (x[I0][J0] == 1) xx += area;
            continue;
        }

        if (I0 == I1)
        {
            if (x[I0][J0] && x[I1][J1])
            xx += ((1LL << (k - 2)) * area);

            continue;
        }

        if (J0 == J1)
        {
            if (x[I0][J0] && x[I1][J1])
            xx += ((1LL << (k - 2)) * area);

            continue;
        }

        U = row(I0 , J0 , J1);
        D = row(I1 , J0 , J1);
        L = column(J0 , I0 , I1);
        R = column(J1 , I0 , I1);

        LU = x[I0][J0];
        RD = x[I1][J1];
        LD = x[I1][J0];
        RU = x[I0][J1];

        L -= LU + LD;
        U -= LU + RU;
        R -= RD + RU;
        D -= RD + LD;

        for (q = 0 ; q < (1 << 4) ; ++q)
        {
            cover = 0;

            if (q & (1 << 0)) // LU
            {
                if (LU == 0) continue;
                cover |= (1 << 0);
                cover |= (1 << 1);
            }

            if (q & (1 << 1)) // RD
            {
                if (RD == 0) continue;
                cover |= (1 << 2);
                cover |= (1 << 3);
            }

            if (q & (1 << 2)) // LD
            {
                if (LD == 0) continue;
                cover |= (1 << 0);
                cover |= (1 << 3);
            }

            if (q & (1 << 3)) // RU
            {
                if (RU == 0) continue;
                cover |= (1 << 1);
                cover |= (1 << 2);
            }

            ans = 1;

            if (cover & (1 << 0)) // L
            ans = 1LL * ans * (1LL << L);
            else ans = 1LL * ans * ((1LL << L) - 1);

            if (cover & (1 << 1)) // U
            ans = 1LL * ans * (1LL << U);
            else ans = 1LL * ans * ((1LL << U) - 1);

            if (cover & (1 << 2)) // R
            ans = 1LL * ans * (1LL << R);
            else ans = 1LL * ans * ((1LL << R) - 1);

            if (cover & (1 << 3)) // D
            ans = 1LL * ans * (1LL << D);
            else ans = 1LL * ans * ((1LL << D) - 1);

            xx += ans * area;
        }
    }

    rr = __gcd(xx , yy);
    xx /= rr , yy /= rr;

    fout << xx << "/" << yy << '\n';
}

return 0;
}