Cod sursa(job #1772815)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 7 octombrie 2016 00:59:09
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.75 kb
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int kMaxN = 55;

int n, m;
int v[kMaxN][kMaxN];
int s[kMaxN][kMaxN];

int getSum(const int Ax, const int Ay, const int Bx, const int By) {
    if (Ax <= Bx && Ay <= By) {
        return s[Bx][By] - s[Ax - 1][By] - s[Bx][Ay - 1] + s[Ax - 1][Ay - 1];
    }
    else {
        return 0;
    }
}

int64_t boundingBox(const int Ax, const int Ay, const int Bx, const int By) {
    if (getSum(Ax, Ay, Bx, By) > 0) {
        if (Ax != Bx && Ay != By) {
            int pCorner[4] = {};
            int pEdge[4] = {};
            int pInside;
            
            pInside = getSum(Ax + 1, Ay + 1, Bx - 1, By - 1);
            pCorner[0] = v[Ax][Ay];
            pCorner[1] = v[Bx][Ay];
            pCorner[2] = v[Bx][By];
            pCorner[3] = v[Ax][By];
            pEdge[0] = getSum(Ax, Ay + 1, Ax, By - 1);
            pEdge[1] = getSum(Ax + 1, Ay, Bx - 1, Ay);
            pEdge[2] = getSum(Bx, Ay + 1, Bx, By - 1);
            pEdge[3] = getSum(Ax + 1, By, Bx - 1, By);
            
            int64_t cnt = 0;
            for (int i = 0; i < 16; i++) {
                int64_t crCnt = 1;
                bool edgeCovered[4] = {};
                bool goodSet = true;
                for (int j = 0; j < 4; j++) {
                    if ((i >> j) & 1) {
                        edgeCovered[j] = true;
                        edgeCovered[(j + 1) & 3] = true;
                        goodSet &= (pCorner[j] == 1);
                    }
                }
                for (int j = 0; j < 4; j++) {
                    int64_t factor = 1LL << pEdge[j];
                    if (!edgeCovered[j]) {
                        factor--;
                    }
                    crCnt *= factor;
                }
                crCnt *= (1LL << pInside) * goodSet;
                cnt += crCnt;
            }
            return cnt;
        }
        else {
            if (Ax == Bx) {
                if (v[Ax][Ay] == 0 || v[Ax][By] == 0) {
                    return 0;
                }
                else {
                    return (1LL << getSum(Ax, Ay + 1, Ax, By - 1));
                }
            }
            else {
                if (v[Ax][Ay] == 0 || v[Bx][Ay] == 0) {
                    return 0;
                }
                else {
                    return (1LL << getSum(Ax + 1, Ay, Bx - 1, Ay));
                }
            }
        }
    }
    else {
        return 0;
    }
}

int main() {
    freopen("boundingbox.in", "r", stdin);
    freopen("boundingbox.out", "w", stdout);
    
    int testCases;
    for (scanf("%d", &testCases); testCases > 0; testCases--) {
        scanf("%d %d", &n, &m);
        
        memset(s, 0, sizeof s);
        memset(v, 0, sizeof v);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                scanf("%1d", &v[i][j]);
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v[i][j];
            }
        }
        
        int64_t sa = 0;
        for (int Ax = 1; Ax <= n; Ax++) {
            for (int Ay = 1; Ay <= m; Ay++) {
                for (int Bx = Ax; Bx <= n; Bx++) {
                    for (int By = Ay; By <= m; By++) {
                        const int64_t nsub = boundingBox(Ax, Ay, Bx, By);
                        sa += 1LL * (Bx - Ax + 1) * (By - Ay + 1) * nsub;
                    }
                }
            }
        }
        
        int64_t num = sa;
        int64_t den = (1LL << getSum(1, 1, n, m));
        while (!(num & 1) && !(den & 1)) {
            num >>= 1;
            den >>= 1;
        }
        
        printf("%lld/%lld\n", num, den);
    }
    
    return 0;
}