# Cod sursa(job #2224098)

Utilizator Data 22 iulie 2018 21:03:43 Boundingbox 0 cpp done Arhiva de probleme 2.68 kb
#include <bits/stdc++.h>

using namespace std;

int x[50][50];
int s[50][50];

int ins(int x1, int y1, int x2, int y2) {
return max(0, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}

int main() {
freopen("boundingbox.in", "r", stdin);
freopen("boundingbox.out", "w", stdout);

int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
long long ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
scanf("%1d", &x[i][j]);
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x[i][j];
ans += x[i][j];
}
for (int i = 1; i <= n; ++i)
for (int j1 = 1; j1 < m; ++j1)
for (int j2 = j1 + 1; j2 <= m; ++j2)
if (x[i][j1] + x[i][j2] == 2)
ans += (j2 - j1 + 1) * (1LL << ins(i, j1 + 1, i, j2 - 1));
for (int j = 1; j <= m; ++j)
for (int i1 = 1; i1 < n; ++i1)
for (int i2 = i1 + 1; i2 <= n; ++i2)
if (x[i1][j] + x[i2][j] == 2)
ans += (i2 - i1 + 1) * (1LL << ins(i1 + 1, j, i2 - 1, j));
for (int i1 = 1; i1 < n; ++i1)
for (int i2 = i1 + 1; i2 <= n; ++i2)
for (int j1 = 1; j1 < m; ++j1)
for (int j2 = j1 + 1; j2 <= m; ++j2) {
int l1 = ins(i1, j1 + 1, i1, j2 - 1);
int l2 = ins(i2, j1 + 1, i2, j2 - 1);
int c1 = ins(i1 + 1, j1, i2 - 1, j1);
int c2 = ins(i1 + 1, j2, i2 - 1, j2);
long long e = (1LL << ins(i1 + 1, j1 + 1, i2 - 1, j2 - 1));
int ar = (i2 - i1 + 1) * (j2 - j1 + 1);
long long aux = 0;
for (int i = 0; i < 16; ++i) {
int a = 0, b = 0, c = 0, d = 0;
if ((i & 1) && !x[i1][j1])
continue;
if ((i & 2) && !x[i1][j2])
continue;
if ((i & 4) && !x[i2][j2])
continue;
if ((i & 8) && !x[i2][j1])
continue;
if ((i & 1) == 0 && (i & 2) == 0)
a = 1;
if ((i & 2) == 0 && (i & 4) == 0)
b = 1;
if ((i & 4) == 0 && (i & 8) == 0)
c = 1;
if ((i & 8) == 0 && (i & 1) == 0)
d = 1;
aux += ((1LL << l1) - a) * ((1LL << c2) - b) * ((1LL << l2) - c) * ((1LL << c1) - d);
}
ans += aux * ar * e;
}
if (ans == 0LL) {
printf("0/1");
} else {
long long nr = (1LL << s[n][m]);
while (nr % 2 == 0 && ans % 2 == 0) {
nr /= 2;
ans /= 2;
}
printf("%lld/%lld\n", ans, nr);
}
memset(s, 0, sizeof(s));
}

return 0;
}