Pagini recente » Cod sursa (job #401821) | Cod sursa (job #863521) | Cod sursa (job #2044476) | Cod sursa (job #2232032) | Cod sursa (job #1230981)
#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,conf;
long long wh[20];
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 < 3 ? x+1 : 0;
}
inline long long give (int conf)
{
return (pw[d[1]]-(conf&1)) * (pw[d[2]]-((conf>>1)&1)) * (pw[d[3]] - ((conf>>2)&1)) * (pw[d[4]]-((conf>>3)&1));
}
long long back (int p)
{
long long s = 1;
if (p == 5)
{
return give(wh[conf]);
}
if (b[p] == 1)
{
conf += (1<<(p-1));
s = back(p+1);
conf -= (1<<(p-1));
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;
for (int i=0; i<16; ++i)
{
for (int k=0; k<4; ++k)
{
take[k] = ((i>>k)&1);
}
for (int k=0; k<4; ++k)
{
if (!take[k] && !take[next(k)])
{
wh[i] += (1<<k);
}
}
}
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";
}
for (int k=1; k<=1000; ++k)
{
fout<<7<<" "<<7<<"\n";
for (int i=1; i<=7; ++i)
{
for (int j=1; j<=7; ++j)
fout<<1;
fout<<"\n";
}
}
}