Pagini recente » Cod sursa (job #1242645) | Cod sursa (job #954838) | Cod sursa (job #1711230) | Cod sursa (job #1602247) | Cod sursa (job #1230874)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
#define NMAX 52
int s[NMAX][NMAX],a[NMAX][NMAX];
long long p[NMAX];
char sir[NMAX];
long long gcd(long long a, long long b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
int sum(int i, int j, int k, int l)
{
if(k<i || l<j)
return 0;
return s[k][l]-s[k][j-1]-s[i-1][l]+s[i-1][j-1];
}
void solve(long long &x, long long &y, int n, int m)
{
int i,j,k,l,sus,jos,st,dr,inside,arie;
long long d;
x=0;
y=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(k=i;k<=n;k++)
for(l=j;l<=m;l++) {
sus=sum(i,j+1,i,l-1);
jos=sum(k,j+1,k,l-1);
st=sum(i+1,j,k-1,j);
dr=sum(i+1,l,k-1,l);
inside=sum(i+1,j+1,k-1,l-1);
arie=(k-i+1)*(l-j+1);
y=0LL+y+1LL*sus*jos*st*dr*p[inside]*arie;
if(a[i][j])
y=0LL+y+1LL*jos*dr*p[inside]*arie;
if(a[k][l])
y=0LL+y+1LL*sus*st*p[inside]*arie;
if(a[i][l])
y=0LL+y+1LL*jos*st*p[inside]*arie;
if(a[k][j])
y=0LL+y+1LL*sus*dr*p[inside]*arie;
if(a[i][j] && a[k][j])
y=0LL+y+1LL*dr*p[inside+st+sus+jos]*arie;
if(a[i][l] && a[k][l])
y=0LL+y+1LL*st*p[inside+dr+sus+jos]*arie;
if(a[i][j] && a[i][l])
y=0LL+y+1LL*jos*p[inside+st+dr+sus]*arie;
if(a[k][j] && a[k][l])
y=0LL+y+1LL*sus*p[inside+st+dr+jos]*arie;
if(i!=k && j!=l) {
if(a[i][j] && a[k][l])
y=0LL+y+p[inside+st+dr+sus+jos]*arie;
if(a[k][j] && a[i][l])
y=0LL+y+p[inside+st+dr+sus+jos]*arie;
if(a[i][j] && a[i][l]) {
if(a[k][l])
y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
if(a[k][j])
y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
}
if(a[k][j] && a[k][l]) {
if(a[i][j])
y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
if(a[i][l])
y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
}
if(a[i][j] && a[i][l] && a[k][j] && a[k][l])
y=0LL+y+1LL*p[inside+sus+jos+st+dr]*arie;
}
else if(i==k) {
if(a[i][j] && a[i][l])
y=0LL+y+1LL*p[sus]*arie;
}
else if(j==l) {
if(a[i][j] && a[k][j])
y=0LL+y+1LL*p[st]*arie;
}
}
x=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j])
x++;
x=p[x];
d=gcd(x,y);
if(d) {
x=1LL*x/d;
y=1LL*y/d;
}
}
int main ()
{
int t,i,n,m,j;
long long x,y;
ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
f>>t;
p[0]=1;
for(i=1;i<=50;i++)
p[i]=1LL*p[i-1]*2;
while(t--) {
f>>n>>m;
for(i=1;i<=n;i++) {
f>>(sir+1);
for(j=1;j<=m;j++)
if(sir[j]=='1')
a[i][j]=1;
else a[i][j]=0;
}
solve(x,y,n,m);
g<<y<<"/"<<x<<'\n';
}
f.close();
g.close();
return 0;
}