Pagini recente » Istoria paginii cn-soft-grigore-moisil/clasament/11-12 | Cod sursa (job #2496680) | Cod sursa (job #2276447) | Cod sursa (job #1880210) | Cod sursa (job #1230767)
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,j,p,q,nr,t,m,k,cm,cM,lm,lM,ok;
int d[55][55];
char a[55][55];
int w[55];
int s;
struct nod
{
int x;
int y;
}v[55];
int main()
{
freopen("boundingbox.in","r",stdin);
freopen("boundingbox.out","w",stdout);
scanf("%d",&t);
while (t--)
{
scanf("%d %d\n",&n,&m);
p=0;
for (i=1;i<=n;i++)
{
gets(a[i]+1);
for (j=1;j<=m;j++)
if (a[i][j]=='1') v[++p].x=i,v[p].y=j;
}
s=p+1;
for (i=1;i<p;i++) for (j=i+1;j<=p;j++)
d[i][j]=d[j][i]=abs(v[i].x-v[j].x)*abs(v[i].y-v[j].y),s=s+d[i][j];
k=1<<p; s=s+(k/2); q=1<<p;
nr=1; s=0;
if (t==6)
i=i;
while (nr<=q)
{
w[0]=0; cm=55; lm=55; cM=0; lM=0; k=nr; ok=0;
while (k)
{
w[++w[0]]=k%2;
k=k/2;
}
for (i=1;i<=p;i++) if ((w[i]==1)&&(i<=w[0]))
lm=min(lm,v[i].x),lM=max(lM,v[i].x),cm=min(cm,v[i].y),cM=max(cM,v[i].y),ok=1;
if (ok) s=s+(cM-cm+1)*(lM-lm+1);
nr++;
}
int D=0,I=0,R=0;
D=s; I=q; R=D%I;
while (R) D=I,I=R,R=D%I;
printf("%d/%d\n",s/I,q/I);
}
return 0;
}