Cod sursa(job #1759174)

Utilizator Ionut.popescuLiviu Rebreanu Ionut.popescu Data 18 septembrie 2016 16:37:16
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

int main() {
	ifstream cin("boundingbox.in");
	ofstream cout("boundingbox.out");
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	
	int num_tests; cin >> num_tests;
	while (num_tests--) {
		vector<pair<int, int>> v;
		int n, m; cin >> n >> m;
		for (int i = 1; i <= n; i += 1) {
			cin.get();
			for (int j = 1; j <= m; j += 1) {
				if (cin.get() == '1') {
					v.push_back(make_pair(i, j));
				}
			}
		}
		long long answer = 0LL;
		for (int i = (1 << v.size()) - 1; i >= 0; i -= 1) {
			int min_x = n, min_y = m, max_x = 1, max_y = 1;
			for (int j = v.size() - 1; j >= 0; j -= 1) {
				if ((i >> j) & 1) {
					min_x = min(min_x, v[j].first);
					min_y = min(min_y, v[j].second);
					max_x = max(max_x, v[j].first);
					max_y = max(max_y, v[j].second);
				}
			}
			answer += (max_x - min_x + 1) * (max_y - min_y + 1);
		}
		int num_1 = int(v.size());
		while (num_1 > 0 && answer > 0LL && answer % 2LL == 0) {
			num_1 -= 1;
			answer /= 2LL;
		}
		cout << answer << '/' << (1LL << num_1) << '\n';
	}
	return 0;
}