Pagini recente » Cod sursa (job #734707) | Cod sursa (job #1897312) | Cod sursa (job #1507325) | Cod sursa (job #2766328) | Cod sursa (job #1230783)
#include <cstdio>
using namespace std;
int v1[5000],v2[5000],t,n,m,i,j,q,x,lim,s,nr,maxx,maxy,minx,miny;
char v[5000];
int main()
{
freopen("boundingbox.in", "r", stdin);
freopen("boundingbox.out", "w", stdout);
for(scanf("%d",&t);t;t--)
{
scanf("%d%d\n",&n,&m);
nr=0;
for(i=1;i<=n;i++)
{
scanf("%s\n",v);
for(j=0;j<m;j++)
if(v[j]=='1')
{
v1[++nr]=i;
v2[nr]=j+1;
}
}
lim=(1<<nr)-1;
s=0;
for(i=1;i<=lim;i++)
{
maxx=maxy=0;
minx=miny=50;
for(j=1,q=1;q<=i;j++,q<<=1)
if(i&q)
{
if(maxx<v1[j]) maxx=v1[j];
if(maxy<v2[j]) maxy=v2[j];
if(minx>v1[j]) minx=v1[j];
if(miny>v2[j]) miny=v2[j];
}
s+=(maxx-minx+1)*(maxy-miny+1);
}
lim++;
while(s%2==0 && lim%2==0)
{
s/=2;
lim/=2;
}
printf("%d/%d\n",s,lim);
}
return 0;
}