Cod sursa(job #1230663)

Utilizator klamathixMihai Calancea klamathix Data 18 septembrie 2014 21:24:19
Problema Boundingbox Scor Ascuns
Compilator cpp Status done
Runda Marime 3.26 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 7;

ll gcd(ll a, ll b) {
    if(!b)
        return a;
    return gcd(b, a % b);
}

vector<vector<int>> sum;

int getSum(int x0, int y0, int x1, int y1) {
    if(x1 < x0 || y1 < y0)
        return 0;
    int ans = sum[x1][y1];
    if(x0 - 1 >= 0)
        ans -= sum[x0 - 1][y1];
    if(y0 - 1 >= 0)
        ans -= sum[x1][y0 - 1];
    if(x0 - 1 >= 0 && y0 - 1 >= 0)
        ans += sum[x0 - 1][y0 - 1];
    return ans;
}

int main() {
    #ifdef INFOARENA
    ifstream cin("boundingbox.in");
    ofstream cout("boundingbox.out");
    #endif

    //ifstream cin("test.in");

    int t; cin >> t;
    while(t--) {
        int n, m; cin >> n >> m;
        vector<string> A(n);
        ll all = 1;
        sum = vector<vector<int>> (n, vector<int> (m, 0));

        for(int i = 0; i < n; ++i) {
            cin >> A[i];
            for(int j = 0; j < m; ++j) {
                if(A[i][j] == '1') {
                    all *= 2;
                    sum[i][j]++;
                }
                if(i - 1 >= 0)
                    sum[i][j] += sum[i - 1][j];
                if(j - 1 >= 0)
                    sum[i][j] += sum[i][j - 1];
                if(i - 1 >= 0&& j - 1 >= 0)
                    sum[i][j] -= sum[i - 1][j - 1];
            }
        }

        vector<int> x(2, 0), y(2, 0);
        ll good = 0;

        for(x[0] = 0; x[0] < n; ++x[0])
            for(y[0] = 0; y[0] < m; ++y[0]) 
                for(x[1] = x[0]; x[1] < n; ++x[1])
                    for(y[1] = y[0]; y[1] < m; ++y[1]) {
                        ll coef = (1LL << getSum(x[0] + 1, y[0] + 1, x[1] - 1, y[1] - 1));
                        //cerr << coef << "\n";

                        vector<int> SL(2, 0), SC(2, 0);
                        SL[0] = getSum(x[0], y[0] + 1, x[0], y[1] - 1);
                        SL[1] = getSum(x[1], y[0] + 1, x[1], y[1] - 1);
                        SC[0] = getSum(x[0] + 1, y[0], x[1] - 1, y[0]);
                        SL[1] = getSum(x[0] + 1, y[1], x[1] - 1, y[1]);

                        for(int mask = 0; mask < 16; ++mask) {
                            bool ok = true;
                            vector<int> hasL(2, 0), hasC(2, 0);

                            for(int i = 0; i < 4; ++i)
                                if((1 << i) & mask) {
                                    if(A[i & 1][(i >> 1) & 1] == '0') 
                                        ok = false;
                                    else 
                                        hasL[i & 1] = 1, hasC[(i >> 1) & 1] = 1;
                                }

                            if(ok == false)
                                continue;

                            ll now = 1;
                            for(int i = 0; i < 2; ++i) {
                                if(hasL[i] == 0)
                                    now *= SL[i];
                                if(hasC[i] == 0)
                                    now *= SC[i];
                            }

                            good += now * coef * (x[1] - x[0] + 1) * (y[1] - y[0] + 1);
                        }
                    }
    
        //cerr << good << "\n";
        ll g = gcd(good, all);
        good /= g, all /= g;
        cout << good << "/" << 2 * all << "\n";
    }
}