Pagini recente » Cod sursa (job #1358069) | Cod sursa (job #464729) | Cod sursa (job #537545) | Cod sursa (job #261723) | Cod sursa (job #1463049)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("boundingbox.in");
ofstream fout("boundingbox.out");
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
const int nmax = 55;
char a[nmax][nmax];
int s[nmax][nmax];
ll two[nmax];
int sum(int i, int j, int k, int l) {
return s[k][l] - s[k][j - 1] - s[i - 1][l] + s[i - 1][j - 1];
}
int main() {
two[0] = 1;
for (int i = 1; i < nmax; i++)
two[i] = 2LL * two[i - 1];
int t;
fin >> t;
for (; t; t--) {
int n, m;
fin >> n >> m;
for (int i = 1; i <= n; i++)
fin >> (a[i] + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j] - '0';
int cnt = 0;
ll total = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
for (int k = i; k <= n; k++)
for (int l = j; l <= m; l++) {
if (i == k && j == l && a[i][j] == '1') {
cnt++;
total++;
} else if (i == k && a[i][j] == '1' && a[i][l] == '1') {
total += two[sum(i, j + 1, i, l - 1)] * (l - j + 1);
} else if (j == l && a[i][j] == '1' && a[k][j] == '1') {
total += two[sum(i + 1, j, k - 1, j)] * (k - i + 1);
} else {
for (int mask = 0; mask < 16; mask++) {
if ((mask & 1) && a[i][j] == '0')
continue;
if ((mask & 2) && a[i][l] == '0')
continue;
if ((mask & 4) && a[k][j] == '0')
continue;
if ((mask & 8) && a[k][l] == '0')
continue;
ll curr = 1;
if ((mask & 1) || (mask & 2))
curr *= 1LL * two[sum(i, j + 1, i, l - 1)];
else
curr *= 1LL * (two[sum(i, j + 1, i, l - 1)] - 1);
if ((mask & 1) || (mask & 4))
curr *= 1LL * two[sum(i + 1, j, k - 1, j)];
else
curr *= 1LL * (two[sum(i + 1, j, k - 1, j)] - 1);
if ((mask & 2) || (mask & 8))
curr *= 1LL * two[sum(i + 1, l, k - 1, l)];
else
curr *= 1LL * (two[sum(i + 1, l, k - 1, l)] - 1);
if ((mask & 4) || (mask & 8))
curr *= 1LL * two[sum(k, j + 1, k, l - 1)];
else
curr *= 1LL * (two[sum(k, j + 1, k, l - 1)] - 1);
total += curr * (k - i + 1) * (l - j + 1);
}
}
}
ll g = __gcd(total, two[cnt]);
fout << total / g << "/" << two[cnt] / g << '\n';
}
return 0;
}