Cod sursa(job #1230902)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 19 septembrie 2014 12:56:44
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.66 kb
#include <fstream>
#include <vector>
using namespace std;

const int MAX_N = 52;

int T, N, M;
int A[MAX_N][MAX_N];
vector < pair < int, int > > v;
char s[MAX_N + 5];

long long gcd(long long a, long long b) {
	while(b) {
		long long r = a % b;

		a = b;
		b = r;
	}

	return a;
}

bool check(int conf, int x1, int y1, int x2, int y2) {
    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;
        else okX2 = 1;
        if(v[i].second == y1)
            okY1 = 1;
        else okY2 = 1;
    }

    return okX1 && okX2 && okY1 && okY2;
}

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

	s[0] = ' ';

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

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

			for(int j = 1; j <= M; ++j) {
				A[i][j] = s[j] - '0';
				if(A[i][j])
                    v.push_back(make_pair(i, j));
			}
		}

		long long a = 0, b = 1;

		int n = v.size();
		for(int conf = 1; conf < (1 << n); ++conf) {
            int x1 = N + 1, x2 = 0, y1 = M + 1, y2 = 0;

            for(int i = 0; i < n; ++i)
                if(conf & (1 << i)) {
                    x1 = min(x1, v[i].first);
                    x2 = max(x2, v[i].first);
                    y1 = min(y1, v[i].second);
                    y2 = max(y2, v[i].second);
                }
                ++b;
                a += (x2 - x1 + 1) * (y2 - y1 + 1);
		}

		int d;
		do {
			d = gcd(a, b);

			a /= d;
			b /= d;
		} while (d != 1);

		g << a << "/" << b << "\n";
	}

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

	return 0;
}