# Cod sursa(job #2224094)

Utilizator Data 22 iulie 2018 20:26:41 Boundingbox 0 cpp done Arhiva de probleme 2.73 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);
int e = (1 << ins(i1 + 1, j1 + 1, i2 - 1, j2 - 1));
int ar = (i2 - i1 + 1) * (j2 - j1 + 1);
long long aux = 0;
if (i1 == 1 && i2 == 2 && j1 == 1 && j2 == 3)
int ok = 1;
for (int i = 0; i < 16; ++i) {
int a = l1, b = c2, c = l2, d = c1;
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--;
if ((i & 2) == 0 && (i & 4) == 0)
b--;
if ((i & 4) == 0 && (i & 8) == 0)
c--;
if ((i & 8) == 0 && (i & 1) == 0)
d--;
aux += (1LL << a) * (1LL << b) * (1LL << c) * (1LL << d) * e;
}
ans += aux * ar;
}
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;
}
``````