Pagini recente » Cod sursa (job #257803) | Cod sursa (job #2167729) | Cod sursa (job #1579862) | Cod sursa (job #2748392) | Cod sursa (job #1230902)
#include <fstream>
#include <vector>
using namespace std;
const int MAX_N = 52;
int T, N, M;
int A[MAX_N][MAX_N];
vector < pair < int, int > > v;
char s[MAX_N + 5];
long long gcd(long long a, long long b) {
while(b) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
bool check(int conf, int x1, int y1, int x2, int y2) {
bool okX1 = 0, okX2 = 0, okY1 = 0, okY2 = 0;
for(int i = 0; i < (int) v.size(); ++i) {
if(!(conf & (1 << i)))
continue;
if(v[i].first == x1)
okX1 = 1;
else okX2 = 1;
if(v[i].second == y1)
okY1 = 1;
else okY2 = 1;
}
return okX1 && okX2 && okY1 && okY2;
}
int main() {
ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
s[0] = ' ';
f >> T;
for(int t = 1; t <= T; ++t) {
f >> N >> M;
v.clear();
for(int i = 1; i <= N; ++i) {
f >> (s + 1);
for(int j = 1; j <= M; ++j) {
A[i][j] = s[j] - '0';
if(A[i][j])
v.push_back(make_pair(i, j));
}
}
long long a = 0, b = 1;
int n = v.size();
for(int conf = 1; conf < (1 << n); ++conf) {
int x1 = N + 1, x2 = 0, y1 = M + 1, y2 = 0;
for(int i = 0; i < n; ++i)
if(conf & (1 << i)) {
x1 = min(x1, v[i].first);
x2 = max(x2, v[i].first);
y1 = min(y1, v[i].second);
y2 = max(y2, v[i].second);
}
++b;
a += (x2 - x1 + 1) * (y2 - y1 + 1);
}
int d;
do {
d = gcd(a, b);
a /= d;
b /= d;
} while (d != 1);
g << a << "/" << b << "\n";
}
f.close();
g.close();
return 0;
}