Cod sursa(job #1230783)
Utilizator | Chichirim George george_stelian | Data | 19 septembrie 2014 11:25:36 |
---|---|---|---|
Problema | Boundingbox | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Infoarena Cup 2014 | Marime | 1.19 kb |
#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;
}