Pagini recente » Cod sursa (job #2407263) | Cod sursa (job #2165098) | Cod sursa (job #1810179) | Cod sursa (job #1176816) | Cod sursa (job #1238481)
#include <stdio.h>
#include <cstring>
#include <algorithm>
#define maxdim 53
using namespace std;
int n, m, ones;
int x[maxdim], y[maxdim];
int main() {
freopen("boundingbox.in", "r", stdin);
freopen("boundingbox.out", "w", stdout);
int tests;
scanf("%d", &tests);
while (tests--) {
scanf("%d %d\n", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
char ch;
scanf("%c", &ch);
if (ch == '1') {
++ones;
x[ones] = i, y[ones] = j;
}
}
scanf("\n");
}
long long D[ones+5][n+5][n+5][m+5][m+5];
memset(D, 0, sizeof(D));
D[0][n][0][m][0] = 1;
for (int i = 0; i < ones; ++i) {
for (int x1 = 0; x1 <= n; ++x1) {
for (int x2 = 0; x2 <= n; ++x2) {
for (int y1 = 0; y1 <= m; ++y1) {
for (int y2 = 0; y2 <= m; ++y2) {
D[i+1][x1][x2][y1][y2] += D[i][x1][x2][y1][y2]; //nu intra in solutie
D[i+1][min(x1, x[i+1])][max(x2, x[i+1])][min(y1, y[i+1])][max(y2, y[i+1])] += D[i][x1][x2][y1][y2];
}
}
}
}
}
long long total_sum = 0;
for (int x1 = 1; x1 <= n; ++x1) {
for (int x2 = x1; x2 <= n; ++x2) {
for (int y1 = 1; y1 <= m; ++y1) {
for (int y2 = y1; y2 <= m; ++y2) {
total_sum += (x2 - x1 + 1) * (y2 - y1 + 1) * D[ones][x1][x2][y1][y2];
}
}
}
}
long long numitor = 1LL << ones;
for (int i = 1; numitor != 1 && !(total_sum & 1); ++i) {
total_sum >>= 1;
numitor >>= 1;
}
printf("%lld/%lld\n", total_sum, numitor);
ones = 0;
}
return 0;
}