Cod sursa(job #1230871)

Utilizator andreiiiiPopa Andrei andreiiii Data 19 septembrie 2014 12:36:09
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.54 kb
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int Nmax = 55;

char A[Nmax];
vector< pair<int, int> > points;
int minx = Nmax, maxx = 0, miny = Nmax, maxy = 0;
int ans;

void back(int pos) {
    if (pos == int(points.size())) {
        if (minx != Nmax)
            ans += (maxx - minx + 1) * (maxy - miny + 1);
    } else {
        int minxs = minx, maxxs = maxx, minys = miny, maxys = maxy;
        minx = min(minx, points[pos].first);
        maxx = max(maxx, points[pos].first);
        miny = min(miny, points[pos].second);
        maxy = max(maxy, points[pos].second);

        back(pos + 1);

        minx = minxs;
        maxx = maxxs;
        miny = minys;
        maxy = maxys;

        back(pos + 1);
    }
}

int gcd(int a, int b) {
    int c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

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

    int T;
    scanf("%d\n", &T);

    while (T--) {
        points.clear();

        int N, M;

        scanf("%d %d\n", &N, &M);
        for (int i = 1; i <= N; ++i) {
            fgets(A + 1, Nmax, stdin);
            for (int j = 1; j <= M; ++j) {
                if (A[j] == '1')
                    points.push_back(make_pair(i, j));
            }
        }

        ans = 0;
        back(0);

        int p = gcd(ans, 1 << points.size());
        printf("%d/%d\n", ans / p, (1 << points.size()) / p);
    }
}