Cod sursa(job #1238547)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 7 octombrie 2014 10:02:13
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 kb
#include <fstream>
#include <vector>
#include <algorithm>

#include <cstdio>
using namespace std;

const int MAX_N = 52;

int T, N, M, cntX1, cntY1, cntX2, cntY2;
int A[MAX_N][MAX_N], S[MAX_N][MAX_N], pow2[62];
vector < pair < int, int > > v, temp;
char s[MAX_N + 5];

int countOnes(int x1, int y1, int x2, int y2) {
    if(x1 > x2 || y1 > y2)
        return 0;

    return S[x2][y2] - S[x2][y1 - 1] - S[x1 - 1][y2] + S[x1 - 1][y1 - 1];
}

long long compute(int conf, int x1, int y1, int x2, int y2) {
    long long ret = 0;
    bool okX1 = 0, okX2 = 0, okY1 = 0, okY2 = 0;
    for(int i = 0; i < (int) v.size(); ++i) {
        if(!(conf & (1 << i)))
            continue;
        if(v[i].first == x1)
            okX1 = 1;
        if(v[i].first == x2)
            okX2 = 1;
        if(v[i].second == y1)
            okY1 = 1;
        if(v[i].second == y2)
            okY2 = 1;
    }

    ret = 1;
    if(okX1)
        ret *= pow2[cntX1];
    else ret *= (pow2[cntX1] - 1);

    if(x1 != x2) {
        if(okX2)
            ret *= pow2[cntX2];
        else ret *= (pow2[cntX2] - 1);
    }

    if(okY1)
        ret *= pow2[cntY1];
    else ret *= (pow2[cntY1] - 1);

    if(y1 != y2) {
        if(okY2)
            ret *= pow2[cntY2];
        else ret *= (pow2[cntY2] - 1);
    }

    return ret;
}

int main() {
    ifstream f("boundingbox.in");
    ofstream g("boundingbox.out");

    s[0] = ' ';

    pow2[0] = 1;
    for(int i = 1; i <= 60; ++i)
        pow2[i] = pow2[i - 1] * 2;

    f >> T;
    for(int t = 1; t <= T; ++t) {
        f >> N >> M;

        for(int i = 1; i <= N; ++i) {
            f >> (s + 1);

            for(int j = 1; j <= M; ++j)
                A[i][j] = s[j] - '0';
        }

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

        long long a = 0, b = 0;
        for(int x1 = 1; x1 <= N; ++x1)
            for(int y1 = 1; y1 <= M; ++y1)
                for(int x2 = x1; x2 <= N; ++x2)
                    for(int y2 = y1; y2 <= M; ++y2) {
                        int inside = countOnes(x1 + 1, y1 + 1, x2 - 1, y2 - 1);

                        cntX1 = countOnes(x1, y1 + 1, x1, y2 - 1);
                        cntX2 = countOnes(x2, y1 + 1, x2, y2 - 1);
                        cntY1 = countOnes(x1 + 1, y1, x2 - 1, y1);
                        cntY2 = countOnes(x1 + 1, y2, x2 - 1, y2);

                        v.clear();
                        temp.clear();
                        if(A[x1][y1])
                            temp.push_back(make_pair(x1, y1));
                        if(A[x1][y2])
                            temp.push_back(make_pair(x1, y2));
                        if(A[x2][y1])
                            temp.push_back(make_pair(x2, y1));
                        if(A[x2][y2])
                            temp.push_back(make_pair(x2, y2));

                        sort(temp.begin(), temp.end());
                        for(int i = 0; i < (int) temp.size(); ++i)
                            if(!i || temp[i] != temp[i - 1])
                                v.push_back(temp[i]);

                        int n = v.size(), area = (x2 - x1 + 1) * (y2 - y1 + 1);
                        for(int conf = 0; conf < (1 << n); ++conf)
                            a += compute(conf, x1, y1, x2, y2) * pow2[inside] * area;
                    }
        b = pow2[countOnes(1, 1, N, M)];

        while(a % 2 == 0 && b % 2 == 0) {
            a /= 2;
            b /= 2;
        }
        g << a << "/" << b << "\n";
    }

    f.close();
    g.close();

    return 0;
}