Pagini recente » Cod sursa (job #2877542) | Cod sursa (job #3245187) | Cod sursa (job #3185581) | Cod sursa (job #3187118) | Cod sursa (job #1230903)
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;
int main() {
//probabil ceva 2 ^ n
ifstream cin("boundingbox.in");
ofstream cout("boundingbox.out");
int T; cin >> T;
for (; T--; ) {
int R, C; cin >> R >> C;
vector <string> M;
for (int i = 0; i < R; ++i) {
string s;cin >> s;
M.push_back(s);
}
vector <pair <int, int> > go;
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
if (M[i][j] == '1') {
go.push_back(make_pair(i, j));
}
}
}
double answer = 0;
for (int i = 1; i < (1 << go.size()); ++i) {
int xmin = 100, ymin = 100;
int xmax = 0, ymax = 0;
for (int j = 0; j < go.size(); ++j) {
if (i & (1 << j)) {
xmin = min(go[j].first, xmin);
xmax = max(go[j].first, xmax);
ymin = min(go[j].second, ymin);
ymax = max(go[j].second, ymax);
}
}
cerr << xmin << " " << ymin << " " << xmax << " " << ymax << "\n";
answer += (xmax - xmin + 1) * (ymax - ymin + 1);
}
int up = answer, down = (1 << go.size());
cerr << up << " " << down << "\n";
int x = __gcd(up, down);
cout << up / x << "/" << down / x << "\n";
}
return 0;
}