Pagini recente » Cod sursa (job #2734559) | Cod sursa (job #3217588) | Cod sursa (job #2356099) | infoarena - te ajutam sa devii olimpic! | Cod sursa (job #1759174)
#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;
}