Pagini recente » Cod sursa (job #2285896) | Cod sursa (job #1782733) | Cod sursa (job #2168968) | Cod sursa (job #63950) | Cod sursa (job #1231083)
#include <cstdio>
using namespace std;
struct Point {
int x, y;
};
int a [55][55], u;
Point P [55];
char s [1001];
Point P1 [55];
int minimx () {
int g = 200000, i;
for (i = 1; i <= u; i ++)
if (P1 [i].x < g)
g = P1 [i].x;
return g;
}
int minimy () {
int g = 200000, i;
for (i = 1; i <= u; i ++)
if (P1 [i].y < g)
g = P1 [i].y;
return g;
}
int maximx () {
int g = -1, i;
for (i = 1; i <= u; i ++)
if (P1 [i].x > g)
g = P1 [i].x;
return g;
}
int maximy () {
int g = -1, i;
for (i = 1; i <= u; i ++)
if (P1 [i].y > g)
g = P1 [i].y;
return g;
}
int gcd (long long x , long long y) {
long long r;
while (y) {
r = x % y;
x = y;
y = r;
}
return x;
}
int main () {
int n, m, i, j, ns = 0, b, v, c, l, h, T, t;
long long aria = 0, cm;
freopen ("boundingbox.in", "r", stdin);
freopen ("boundingbox.out", "w", stdout);
scanf ("%d", &T);
for (t = 1; t <= T; t ++) {
u = aria = ns = cm = 0;
scanf ("%d%d\n", &n, &m);
for (i = 1; i <= n; i ++) {
gets (s + 1);
for (j = 1; j <= m; j ++) {
a [i][j] = s [j] - '0';
if (a [i][j] == 1) {
ns ++;
P [++ u].x = i;
P [u].y = j;
}
}
}
c = ns;
ns = (1 << ns);
for (v = 1; v < ns; v ++) {
u = 0;
for (b = 0; b < c; b ++)
if (v & (1 << b)) {
P1 [++ u] = P [b + 1];
}
l = maximx () - minimx () + 1;
h = maximy () - minimy () + 1;
aria = (long long)aria + l * h;
}
c = ns;
cm = gcd (aria, c);
if (cm) {
aria = aria / cm;
c = c / cm;
}
printf ("%lld", aria);
printf ("/");
printf ("%d\n", c);
}
return 0;
}