Pagini recente » Cod sursa (job #2204026) | Cod sursa (job #3235239) | Cod sursa (job #548159) | Cod sursa (job #2610604) | Cod sursa (job #1230821)
#include<cstdio>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<unordered_map>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
int t, n, m, cnt, i, j, lim, cmin, cmax, rmin, rmax, mlc, g, x[20], y[20];
char a[55][55];
ll sol;
ll gcd(ll a, ll b)
{
ll r;
while(b)
{
r = a % b;
a = b;
b = r;
}
return a;
}
int main()
{
freopen("boundingbox.in", "r", stdin);
freopen("boundingbox.out", "w", stdout);
scanf("%d", &t);
for(; t; t--)
{
scanf("%d%d", &n, &m);
cnt = -1;
for(i = 1; i <= n; i++)
{
scanf("%s", a[i] + 1);
for(j = 1; j <= m; j++)
{
if(a[i][j] == '1')
{
cnt++;
x[cnt] = i;
y[cnt] = j;
}
}
}
sol = 0;
cnt++;
lim = 1 << cnt;
for(i = 1; i < lim; i++)
{
rmin = n + 1;
rmax = 0;
cmin = m + 1;
cmax = 0;
for(j = 0; j < cnt; j++)
if((1 << j) & i)
{
rmin = min(rmin, x[j]);
rmax = max(rmax, x[j]);
cmin = min(cmin, y[j]);
cmax = max(cmax, y[j]);
}
sol += 1LL * (rmax - rmin + 1) * (cmax - cmin + 1);
}
mlc = 1;
for(i = 1; i <= cnt; i++)
mlc *= 2;
g = gcd(sol, mlc);
printf("%lld/%d\n", sol / g, mlc / g);
}
return 0;
}