Pagini recente » Cod sursa (job #1298262) | Cod sursa (job #708545) | Cod sursa (job #2797583) | Cod sursa (job #1762328) | Cod sursa (job #1230943)
#include <fstream>
#define maxn 55
using namespace std;
ifstream fin ("boundingbox.in");
ofstream fout ("boundingbox.out");
int a[maxn][maxn];
char s[maxn][maxn];
int b[10],d[10],r,c,take[10],test;
long long ans,pw[maxn];
int sub (int i, int j, int k, int h)
{
if (i > j || k > h)
return 0;
return a[j][h] - a[i-1][h] - a[j][k-1] + a[i-1][k-1];
}
inline int next (int x)
{
return x < 4 ? x+1 : 1;
}
long long back (int p)
{
long long s = 1;
if (p == 5)
{
for (int i=1; i<=4; ++i)
{
if (!take[i] && !take[next(i)])
{
s *= pw[d[i]]-1;
}
else s *= pw[d[i]];
}
return s;
}
if (b[p] == 1)
{
take[p] = 1;
s = back(p+1);
take[p] = 0;
s += back(p+1);
}
else s = back (p+1);
return s;
}
long long cmmdc (long long a, long long b)
{
if (b == 0) return a;
return cmmdc (b,a%b);
}
int main()
{
pw[0] = 1;
for (int i=1; i<=50; ++i)
pw[i] = pw[i-1]*2;
fin>>test;
for (;test; --test)
{
fin>>r>>c;
for (int i=1; i<=r ; ++i)
fin>>s[i]+1;
for (int i=1; i<=r; ++i)
{
for (int j=1; j<=c; ++j)
{
a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + (s[i][j]-'0');
}
}
ans = 0;
for (int i=1; i <= r; ++i)
{
for (int j=i; j<=r; ++j)
{
for (int k=1; k<=c; ++k)
{
for (int h=k; h <= c; ++h)
{
if (j == i && k == h)
{
if (s[i][k] == '1')
ans += 1;
}
else if (j == i)
{
if (s[i][k] == '1' && s[i][h] == '1')
ans += (h-k+1)*(pw[sub(i,j,k,h)-2]);
}
else if (k == h)
{
if (s[i][k] == '1' && s[j][k] == '1')
ans += (j-i+1)*(pw[sub(i,j,k,h)-2]);
}
else
{
b[1] = s[i][k]-'0';
b[2] = s[i][h]-'0';
b[3] = s[j][h]-'0';
b[4] = s[j][k]-'0';
d[1] = sub (i,i,k+1,h-1);
d[2] = sub (i+1,j-1,h,h);
d[3] = sub (j,j,k+1,h-1);
d[4] = sub (i+1,j-1,k,k);
ans += back (1)*(j-i+1)*(h-k+1)*pw[sub(i+1,j-1,k+1,h-1)];
}
}
}
}
}
long long num = pw[a[r][c]];
fout<<ans/cmmdc(ans,num)<<"/"<<num/cmmdc(ans,num)<<"\n";
}
}