Pagini recente » Cod sursa (job #1514615) | Cod sursa (job #1888927) | Cod sursa (job #1708407) | Cod sursa (job #159678) | Cod sursa (job #1230930)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 55;
int T, N, M, X[NMAX], Y[NMAX], K;
char S[NMAX][NMAX];
long long Ans;
long long GCD(long long A, long long B)
{
if(!B) return A;
return GCD(B, A % B);
}
int main()
{
freopen("boundingbox.in", "r", stdin);
freopen("boundingbox.out", "w", stdout);
scanf("%i", &T);
for(; T; T --)
{
Ans = 0;
K = 0;
scanf("%i %i\n", &N, &M);
for(int i = 1; i <= N; ++ i)
{
gets(S[i] + 1);
for(int j = 1; j <= M; ++ j)
if(S[i][j] == '1')
X[K] = i, Y[K ++] = j;
}
for(int Conf = 1; Conf < (1 << K); ++ Conf)
{
int MinX = N + 1, MaxX = 0, MinY = M + 1, MaxY = 0;
for(int i = 0; i < K; ++ i)
if(Conf & (1 << i))
{
MinX = min(MinX, X[i]);
MaxX = max(MaxX, X[i]);
MinY = min(MinY, Y[i]);
MaxY = max(MaxY, Y[i]);
}
Ans += 1LL * (MaxX - MinX + 1) * (MaxY - MinY + 1);
}
long long Up = Ans, Down = (1LL << K), NowGCD = GCD(Up, Down);
Up /= NowGCD;
Down /= NowGCD;
printf("%lld/", Up);
printf("%lld\n", Down);
}
}