Cod sursa(job #1230959)

Utilizator visanrVisan Radu visanr Data 19 septembrie 2014 13:39:54
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 4.28 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int NMAX = 55;

int T, N, M, Sum[NMAX][NMAX];
char S[NMAX][NMAX];
long long Ans;

long long GCD(long long A, long long B)
{
    if(!B) return A;
    return GCD(B, A % B);
}

int Query(int X1, int Y1, int X2, int Y2)
{
    if(X1 > X2 || Y1 > Y2) return 0;
    return Sum[X2][Y2] - Sum[X1 - 1][Y2] - Sum[X2][Y1 - 1] + Sum[X1 - 1][Y1 - 1];
}

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

    scanf("%i", &T);
    for(; T; T --)
    {
        for(int i = 1; i <= N; ++ i)
            for(int j = 1; j <= M; ++ j)
                Sum[i][j] = 0;
        Ans = 0;

        int Cnt1 = 0;

        scanf("%i %i\n", &N, &M);
        for(int i = 1; i <= N; ++ i)
        {
            gets(S[i] + 1);
            for(int j = 1; j <= M; ++ j)
            {
                Cnt1 += S[i][j] == '1';
                Sum[i][j] = Sum[i - 1][j] + Sum[i][j - 1] - Sum[i - 1][j - 1] + (S[i][j] == '1');
            }
        }

        for(int i = 1; i <= N; ++ i)
            for(int left = 1; left <= M; ++ left)
                    for(int j = i + 1; j <= N; ++ j)
                        for(int right = left + 1; right <= M; ++ right)
                        {
                            if(Query(i, left, i, right) == 0 || Query(j, left, j, right) == 0 || Query(i, left, j, left) == 0 || Query(i, right, j, right) == 0)
                                continue;
                            int B1 = S[i][left] == '1', B2 = S[i][right] == '1', B3 = S[j][left] == '1', B4 = S[j][right] == '1';
                            int UpNr = Query(i, left, i, right), DownNr = Query(j, left, j, right);
                            int LeftNr = Query(i, left, j, left), RightNr = Query(i, right, j, right);
                            int Total = UpNr + DownNr + LeftNr + RightNr - B1 - B2 - B3 - B4;
                            int Interior = Query(i + 1, left + 1, j - 1, right - 1);
                            long long Now = 0;
                            for(int Conf = 0; Conf < 16; ++ Conf)
                            {
                                int NowTotal = Total, CntB = 0;
                                if(Conf & 1) NowTotal -= UpNr, CntB ++;
                                if(Conf & 2) NowTotal -= DownNr, CntB ++;
                                if(Conf & 4) NowTotal -= LeftNr, CntB ++;
                                if(Conf & 8) NowTotal -= RightNr, CntB ++;
                                if((Conf & 1) && (Conf & 4)) NowTotal += B1;
                                if((Conf & 1) && (Conf & 8)) NowTotal += B2;
                                if((Conf & 2) && (Conf & 4)) NowTotal += B3;
                                if((Conf & 2) && (Conf & 8)) NowTotal += B4;
                                if(CntB % 2 == 0) Now += (1LL << NowTotal);
                                else Now -= (1LL << NowTotal);
                            }
                            Ans += 1LL * (right - left + 1) * (j - i + 1) * Now * (1LL << Interior);
                        }

        for(int i = 1; i <= N; ++ i)
            for(int j = 1; j <= M; ++ j)
                if(S[i][j] == '1')
                    for(int k = j; k <= M; ++ k)
                        if(S[i][k] == '1')
                        {
                            if(j == k) Ans ++;
                            else
                            {
                                int Interior = Query(i, j + 1, i, k - 1);
                                Ans += (k - j + 1) * (1LL << Interior);
                            }
                        }
        for(int j = 1; j <= M; ++ j)
            for(int i = 1; i <= N; ++ i)
                if(S[i][j] == '1')
                    for(int k = i + 1; k <= N; ++ k)
                        if(S[k][j] == '1')
                        {
                            int Interior = Query(i + 1, j, k - 1, j);
                            Ans += 1LL * (k - i + 1) * (1LL << Interior);
                        }

        long long Up = Ans, Down = (1LL << Cnt1), NowGCD = GCD(Up, Down);
        Up /= NowGCD;
        Down /= NowGCD;

        printf("%lld/", Up);
        printf("%lld\n", Down);
    }
}