Cod sursa(job #1961855)

Utilizator KONT_testekobol Vasile KONT_teste Data 11 aprilie 2017 13:40:57
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <bits/stdc++.h>
using namespace std;
#define maxdim 105
int n, m;
int x[maxdim], y[maxdim]; char sir[maxdim];
long long D[maxdim][maxdim][maxdim];

#define max(a, b) (a >= b ? a : b)
#define min(a, b) (a <= b ? a : b)

int main() {

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

    int tests;
    scanf("%d", &tests);
    while (tests--) {

        scanf("%d %d\n", &n, &m);
        int ones = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%s", sir+1);
            for (int j = 1; j <= m; ++j) {
                char ch = sir[j];
                if (ch == '1') {
                    ++ones;
                    x[ones] = i, y[ones] = j;
                }
            }
            scanf("\n");
        }

        for (int i = 1; i <= ones; ++i) {
            for (int x1 = 1; x1 <= n; ++x1) {
                for (int x2 = x1; x2 <= n; ++x2) {
                    for (int y1 = 1; y1 <= m; ++y1) {
                        for (int y2 = y1; y2 <= m; ++y2) {
                            D[i][x1 * m + y1][x2 * m + y2] = 0;
                        }
                    }
                }
            }
        }

        for (int i = 0; i < ones; ++i) {

            for (int x1 = 1; x1 <= n; ++x1) {
                int updx1 = min(x1, x[i+1]);
                for (int x2 = x1; x2 <= n; ++x2) {
                    int updx2 = max(x2, x[i+1]);
                    for (int y1 = 1; y1 <= m; ++y1) {
                        int updy1 = min(y1, y[i+1]);
                        for (int y2 = y1; y2 <= m; ++y2) {
                            long long val = D[i][x1 * m + y1][x2 * m + y2];
                            if (val == 0) {
                                continue;
                            }
                            int updy2 = max(y2, y[i+1]);

                            D[i+1][x1 * m + y1][x2 * m + y2] += val; //nu intra in solutie
                            D[i+1][updx1 * m + updy1][updx2 * m + updy2] += val;
                        }
                    }
                }
            }

            D[i+1][x[i+1]*m+y[i+1]][x[i+1]*m+y[i+1]] += 1;
        }

        long long total_sum = 0;
        for (int x1 = 1; x1 <= n; ++x1) {
            for (int x2 = x1; x2 <= n; ++x2) {
                for (int y1 = 1; y1 <= m; ++y1) {
                    for (int y2 = y1; y2 <= m; ++y2) {

                        total_sum += (x2 - x1 + 1) * (y2 - y1 + 1) * D[ones][x1 * m + y1][x2 * m + y2];
                    }
                }
            }
        }

        long long numitor = 1LL << ones;
        for (int i = 1; numitor != 1 && !(total_sum & 1); ++i) {
            total_sum >>= 1;
            numitor >>= 1;
        }

        printf("%lld/%lld\n", total_sum, numitor);
    }

    return 0;
}