Cod sursa(job #2121563)

Utilizator amarghescuAnton Marghescu amarghescu Data 3 februarie 2018 20:56:25
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include<cstdio>
char ch[55];
int v[55][55];
int sp[55][55];
int sum(int l1,int c1,int l2,int c2){
return sp[l2][c2]-sp[l1-1][c2]-sp[l2][c1-1]+sp[l1-1][c1-1];}
long long cmmdc(long long a,long long b){
long long r=0;
while(b){
r=a%b;
a=b;
b=r;}
return a;}
int main(){
freopen("boundingbox.in","r",stdin);
freopen("boundingbox.out","w",stdout);
int t,i1,n,m,i,j,pct1,pct2,pct3,pct4,l1,l2,c1,c2,lin1,lin2,lin3,lin4,caz;
long long rasp,ans=0,raspaux,num;
scanf("%d",&t);
for(i1=1;i1<=t;i1++){
scanf("%d%d\n",&n,&m);
for(i=1;i<=n;i++){
fgets(ch+1,52,stdin);
for(j=1;j<=m;j++)
v[i][j]=ch[j]-48;}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
sp[i][j]=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1]+v[i][j];
rasp=0;
raspaux=0;
ans=0;
for(l1=1;l1<=n;l1++)
for(c1=1;c1<=m;c1++)
for(l2=l1;l2<=n;l2++)
for(c2=c1;c2<=m;c2++){
if (l1==1 && l2==2 && c1==1 && c2==3)
l1=1;
if (l1==l2 && c1==c2){
rasp=rasp+v[l1][c1];
continue;}
if (l1==l2){
rasp=rasp+1LL*v[l1][c1]*v[l1][c2]*(1LL<<sum(l1,c1+1,l1,c2-1))*(c2-c1+1);
continue;}
if (c1==c2){
rasp=rasp+1LL*v[l1][c1]*v[l2][c1]*(1LL<<sum(l1+1,c1,l2-1,c1))*(l2-l1+1);
continue;}
raspaux=0;
for(caz=0;caz<=15;caz++){
if (caz==3)
caz=3;
pct1=pct2=pct3=pct4=0;
if ((caz&1)!=0)
pct1=1;
if ((caz&(1<<1))!=0)
pct2=1;
if ((caz&(1<<2))!=0)
pct3=1;
if ((caz&(1<<3))!=0)
pct4=1;
if (pct1==1 && v[l1][c1]==0)
continue;
if (pct2==1 && v[l1][c2]==0)
continue;
if (pct3==1 && v[l2][c1]==0)
continue;
if (pct4==1 && v[l2][c2]==0)
continue;
lin1=lin2=lin3=lin4=0;
if (pct1==1)
lin1=lin2=1;
if (pct2==1)
lin1=lin4=1;
if (pct3==1)
lin2=lin3=1;
if (pct4==1)
lin3=lin4=1;
ans=1LL<<sum(l1+1,c1+1,l2-1,c2-1);
if (lin1==1)
ans=ans*(1LL<<sum(l1,c1+1,l1,c2-1));
else
ans=ans*((1LL<<sum(l1,c1+1,l1,c2-1))-1);
if (lin2==1)
ans=ans*(1LL<<sum(l1+1,c1,l2-1,c1));
else
ans=ans*((1LL<<sum(l1+1,c1,l2-1,c1))-1);
if (lin3==1)
ans=ans*(1LL<<sum(l2,c1+1,l2,c2-1));
else
ans=ans*((1LL<<sum(l2,c1+1,l2,c2-1))-1);
if (lin4==1)
ans=ans*(1LL<<sum(l1+1,c2,l2-1,c2));
else
ans=ans*((1LL<<sum(l1+1,c2,l2-1,c2))-1);
raspaux=raspaux+ans;}
rasp=rasp+1LL*raspaux*(l2-l1+1)*(c2-c1+1);}
num=1LL<<sum(1,1,n,m);
printf("%lld/%lld\n",rasp/cmmdc(rasp,num),num/cmmdc(rasp,num));}
return 0;}