Cod sursa(job #1495977)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 4 octombrie 2015 00:37:51
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.4 kb
#include <cstdio>
#define DIM 64
using namespace std;

int T, N, M, is, ij, js, jj;
char A[DIM][DIM];
int  D[DIM][DIM];
long long nr, nr2;

int sum(int is, int js, int ij, int jj){
    if(ij < is || jj < js) return 0;
    return D[ij][jj] - D[is-1][jj] - D[ij][js-1] + D[is-1][js-1];
}

void f1(int val){
    nr2 = nr2 * 1LL * ((1LL<<sum(is, js+1, is, jj-1))-val);
    return;
}

void f2(int val){
    nr2 = nr2 * 1LL * ((1LL<<sum(ij, js+1, ij, jj-1))-val);
    return;
}

void f3(int val){
    nr2 = nr2 * 1LL * ((1LL<<sum(is+1, js, ij-1, js))-val);
    return;
}

void f4(int val){
    nr2 = nr2 * 1LL * ((1LL<<sum(is+1, jj, ij-1, jj))-val);
    return;
}

int main(){

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

    scanf("%d", &T);
    for(int t = 1; t <= T; t ++){

        scanf("%d %d", &N, &M);
        for(int i = 1; i <= N; i ++){
            scanf("%s", A[i] + 1);
            for(int j = 1; j <= M; j ++)
                A[i][j] -= '0';
        }

        for(int i = 1; i <= N; i ++)
            for(int j = 1; j <= M; j ++)
                D[i][j] = A[i][j] + D[i][j-1] + D[i-1][j] - D[i-1][j-1];

        long long S = 0;
        for(int L = 1; L <= N; L ++)
            for(int C = 1; C <= M; C ++)
                for(is = 1, ij = is + L - 1; ij <= N; is ++, ij ++)
                    for(js = 1, jj = js + C - 1; jj <= M; js ++, jj ++)
                        if( sum(is, js, is, jj) && sum(is, js, ij, js) && sum(is, jj, ij, jj) && sum(ij, js, ij, jj) ) {

                            if(L == 1 && C == 1)
                                if(A[is][js])
                                    S ++;

                            if(L == 1 && C != 1)
                                if(A[is][js] && A[is][jj])
                                    S += (jj - js + 1) * 1LL * (1LL<<sum(is, js+1, is, jj-1));

                            if(L != 1 && C == 1)
                                if(A[is][js] && A[ij][js])
                                    S += (ij - is + 1) * 1LL * (1LL<<sum(is+1, js, ij-1, js));

                            if(L != 1 && C != 1){
                                nr = 0;

                                if(true){ nr2 = 1; f1(1); f2(1); f3(1); f4(1); nr += nr2; }

                                if(A[is][js]){ nr2 = 1; f1(0); f2(1); f3(0); f4(1); nr += nr2; }
                                if(A[is][jj]){ nr2 = 1; f1(0); f2(1); f3(1); f4(0); nr += nr2; }
                                if(A[ij][js]){ nr2 = 1; f1(1); f2(0); f3(0); f4(1); nr += nr2; }
                                if(A[ij][jj]){ nr2 = 1; f1(1); f2(0); f3(1); f4(0); nr += nr2; }

                                if(A[is][js] && A[is][jj]){ nr2 = 1; f1(0); f2(1); f3(0); f4(0); nr += nr2; }
                                if(A[is][js] && A[ij][js]){ nr2 = 1; f1(0); f2(0); f3(0); f4(1); nr += nr2; }
                                if(A[is][js] && A[ij][jj]){ nr2 = 1; f1(0); f2(0); f3(0); f4(0); nr += nr2; }
                                if(A[is][jj] && A[ij][js]){ nr2 = 1; f1(0); f2(0); f3(0); f4(0); nr += nr2; }
                                if(A[is][jj] && A[ij][jj]){ nr2 = 1; f1(0); f2(0); f3(1); f4(0); nr += nr2; }
                                if(A[ij][js] && A[ij][jj]){ nr2 = 1; f1(1); f2(0); f3(0); f4(0); nr += nr2; }

                                if(A[is][js] && A[is][jj] && A[ij][js]){ nr2 = 1; f1(0); f2(0); f3(0); f4(0); nr += nr2; }
                                if(A[is][js] && A[is][jj] && A[ij][jj]){ nr2 = 1; f1(0); f2(0); f3(0); f4(0); nr += nr2; }
                                if(A[is][js] && A[ij][js] && A[ij][jj]){ nr2 = 1; f1(0); f2(0); f3(0); f4(0); nr += nr2; }
                                if(A[is][jj] && A[ij][js] && A[ij][jj]){ nr2 = 1; f1(0); f2(0); f3(0); f4(0); nr += nr2; }

                                if(A[is][js] && A[is][jj] && A[ij][js] && A[ij][jj]){ nr2 = 1; f1(0); f2(0); f3(0); f4(0); nr += nr2; }

                                nr = nr * (1LL<<sum(is+1, js+1, ij-1, jj-1));
                                S += (ij - is + 1) * (jj - js + 1) * 1LL * nr;
                            }

                        }

        nr = (1LL<<sum(1, 1, N, M));
        while(S % 2 == 0 && nr % 2 == 0){
            S /= 2;
            nr /= 2;
        }

        printf("%lld/%lld\n", S, nr);

    }

    fclose(stdin );
    fclose(stdout);

    return 0;
}