Cod sursa(job #1230984)

Utilizator harababurelPuscas Sergiu harababurel Data 19 septembrie 2014 13:50:15
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.64 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define nmax 55
#define ll long long
using namespace std;

int n, m, t, st[nmax];
char a[nmax][nmax];
vector <pair <int, int> > ones;
ll totalArea = 0LL, configs = 0LL, simp;

void solve() {
	int left=0, right=0, up=0, down=0;

	for(int i=0; i<int(ones.size()); i++) {
		if(!st[i]) continue;

		if(left == 0) left = ones[i].second;
		else left = min(left, ones[i].second);

		if(right == 0) right = ones[i].second;
		else right = max(right, ones[i].second);

		if(up == 0) up = ones[i].first;
		else up = min(up, ones[i].first);

		if(down == 0) down = ones[i].first;
		else down = max(down, ones[i].first);
	}
	
	totalArea += (down-up+1) * (right-left+1);
	configs++;
	/*
	cout<<"am luat unurile: ";
	for(int i=0; i<int(ones.size()); i++) if(st[i]) cout<<i<<" "; cout<<"\n"; 
	cout<<"left="<<left<<" | right="<<right<<" | up="<<up<<" | down="<<down<<"\n";
	cout<<"imi acopera aria: "<<(down-up+1)*(right-left+1)<<"\n\n";
	*/
}

void back(int k) {
	for(int i=1; i>=0; i--) {
		st[k] = i;
		if(k == ones.size()-1) solve();
		else back(k+1);
	}
}

ll cmmdc(ll a, ll b) {
	if(b == 0LL) return a;
	return cmmdc(b, a%b);
}

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

	f>>t;
	while(t--) {
		ones.clear();
		totalArea = 0LL;
		configs = 0LL;

		f>>n>>m;
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++) {
				f>>a[i][j];
				if(a[i][j] == '1') ones.push_back(make_pair(i, j));
			}

		if(ones.size() == 0) totalArea = 1LL, configs = 1LL;
		else back(0);
		totalArea--;

		simp = cmmdc(totalArea, configs);
		g<<(totalArea/simp)<<"/"<<(configs/simp)<<"\n";
	}

	return 0;
}