Pagini recente » Cod sursa (job #750688) | Cod sursa (job #1791899) | Cod sursa (job #143017) | Cod sursa (job #2506446) | Cod sursa (job #1230759)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#define pe pair<int, int>
#define fi first
#define se second
#define mp make_pair
using namespace std;
ifstream fin("boundingbox.in");
ofstream fout("boundingbox.out");
const int MAX_N = 51;
string a[MAX_N];
long long A;
long long B;
long long cmmdc(long long a, long long b) {
while(b) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
void solve(int n, int m) {
vector<pe> v;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(a[i][j] == '1') {
v.push_back(mp(i,j));
}
}
}
B = ((long long) 1 << v.size());
for(long long i = 1; i < B; i++) {
int x1 = n, x2 = 0, y1 = m, y2 = 0;
for(int j = 0; j < (int)v.size(); j++) {
if(i & ((long long)1 << j)) {
x1 = min(x1, v[j].fi);
x2 = max(x2, v[j].fi);
y1 = min(y1, v[j].se);
y2 = max(y2, v[j].se);
}
}
A += (x2 - x1 + 1) * (y2 - y1 + 1);
}
}
int main() {
int t;
fin >> t;
for(int k = 1; k <= t; k++) {
A = 0;
B = 0;
int n, m;
fin >> n >> m;
for(int i = 0; i <= n; i++) {
getline(fin, a[i]);
//cout << a[i] << endl;
a[i] = ' ' + a[i];
}
solve(n, m);
long long d = cmmdc(A, B);
fout << A/d << '/' << B/d << '\n';
}
}