Pagini recente » Cod sursa (job #2911018) | Cod sursa (job #1544380) | Cod sursa (job #2506568) | Cod sursa (job #1094933) | Cod sursa (job #1230927)
#include<cstdio>
using namespace std;
char mat[55][55];
int dreptmat[55][55];
long long put[55];
long long rez;
void solve(int i1, int j1, int i2, int j2, int cod)
{
int liniejos, liniesus, coloanast, coloanadr, interior;
long long rezi;
liniejos = dreptmat[i2][j2 - 1] - dreptmat[i2 - 1][j2 - 1] - dreptmat[i2][j1] + dreptmat[i2 - 1][j1];
liniesus = dreptmat[i1][j2 - 1] - dreptmat[i1 - 1][j2 - 1] - dreptmat[i1][j1] + dreptmat[i1 - 1][j1];
coloanast = dreptmat[i2 - 1][j1] - dreptmat[i1][j1] - dreptmat[i2 - 1][j1 - 1] + dreptmat[i1][j1 - 1];
coloanadr = dreptmat[i2 - 1][j2] - dreptmat[i1][j2] - dreptmat[i2 - 1][j2 - 1] + dreptmat[i1][j2 - 1];
interior = dreptmat[i2 - 1][j2 - 1] - dreptmat[i2 - 1][j1] - dreptmat[i1][j2 - 1] + dreptmat[i1][j1];
switch(cod)
{
case 0:
{
rezi = (put[liniesus] - 1) * (put[coloanadr] - 1) * (put[liniejos] - 1) * (put[coloanast] - 1) * put[interior];
break;
}
case 1:
{
rezi = put[coloanast] * put[liniesus] * (put[coloanadr] - 1) * (put[liniejos] - 1) * put[interior];
break;
}
case 2:
{
rezi = put[coloanadr] * put[liniesus] * (put[coloanast] - 1) * (put[liniejos] - 1) * put[interior];
break;
}
case 3:
{
rezi = put[liniesus] * put[coloanadr] * put[coloanast] * (put[liniejos] - 1) * put[interior];
break;
}
case 4:
{
rezi = put[liniejos] * put[coloanadr] * (put[coloanast] - 1) * (put[liniesus] - 1) * put[interior];
break;
}
case 5:
{
rezi = put[liniejos] * put[liniesus] * put[coloanadr] * put[coloanast] * put[interior];
break;
}
case 6:
{
rezi = (put[coloanast] - 1) * put[coloanadr] * put[liniejos] * put[liniesus] * put[interior];
break;
}
case 7:
{
rezi = put[liniejos] * put[liniesus] * put[coloanadr] * put[coloanast] * put[interior];
break;
}
case 8:
{
rezi = (put[liniesus] - 1) * (put[coloanadr] - 1) * put[liniejos] * put[coloanast] * put[interior];
break;
}
case 9:
{
rezi = (put[coloanadr] - 1) * put[coloanast] * put[liniejos] * put[liniesus] * put[interior];
break;
}
case 10:
{
rezi = put[liniejos] * put[liniesus] * put[coloanadr] * put[coloanast] * put[interior];
break;
}
case 11:
{
rezi = put[liniejos] * put[liniesus] * put[coloanadr] * put[coloanast] * put[interior];
break;
}
case 12:
{
rezi = (put[liniesus] - 1) * put[liniejos] * put[coloanadr] * put[coloanast] * put[interior];
break;
}
case 13:
{
rezi = put[liniejos] * put[liniesus] * put[coloanadr] * put[coloanast] * put[interior];
break;
}
case 14:
{
rezi = put[liniejos] * put[liniesus] * put[coloanadr] * put[coloanast] * put[interior];
break;
}
case 15:
{
rezi = put[liniejos] * put[liniesus] * put[coloanadr] * put[coloanast] * put[interior];
break;
}
}
if(rezi > 0)
rez = rez + (long long)rezi * (i2 - i1 + 1) * (j2 - j1 + 1);
}
int main()
{
freopen("boundingbox.in", "r", stdin);
freopen("boundingbox.out", "w", stdout);
int t, l, i, j, r, c, i1, i2, j1, j2, colt1, colt2, colt3, colt4, nr1;
scanf("%d", &t);
put[0] = 1;
for(i = 1; i <= 50; ++ i)
put[i] = put[i - 1] * 2;
for(l = 1; l <= t; ++ l)
{
rez = 0;
scanf("%d%d\n", &r, &c);
nr1 = 0;
for(i = 1; i <= r; ++ i)
{
for(j = 1; j <= c; ++ j)
{
scanf("%c", &mat[i][j]);
mat[i][j] -= 48;
if(mat[i][j] == 1)
++ nr1;
}
scanf("\n");
}
for(i = 1; i <= r; ++ i)
for(j = 1; j <= c; ++ j)
dreptmat[i][j] = dreptmat[i - 1][j] + dreptmat[i][j - 1] - dreptmat[i - 1][j - 1] + mat[i][j];
for(i1 = 1; i1 < r; ++ i1)
for(j1 = 1; j1 < c; ++ j1)
for(i2 = i1 + 1; i2 <= r; ++ i2)
for(j2 = j1 + 1; j2 <= c; ++ j2)
for(colt1 = 0; colt1 <= mat[i1][j1]; ++ colt1)
for(colt2 = 0; colt2 <= mat[i1][j2]; ++ colt2)
for(colt3 = 0; colt3 <= mat[i2][j2]; ++ colt3)
for(colt4 = 0; colt4 <= mat[i2][j1]; ++ colt4)
solve(i1, j1, i2, j2, colt1 + 2 * colt2 + 4 * colt3 + 8 * colt4);
for(i = 1; i <= r; ++ i)
for(j1 = 1; j1 < c; ++ j1)
if(mat[i][j1] == 1)
for(j2 = j1 + 1; j2 <= c; ++ j2)
if(mat[i][j2] == 1)
rez += (long long)(put[dreptmat[i][j2 - 1] - dreptmat[i][j1] - dreptmat[i - 1][j2 - 1] + dreptmat[i - 1][j1]]) * (j2 - j1 + 1);
for(j = 1; j <= c; ++ j)
for(i1 = 1; i1 < r; ++ i1)
if(mat[i1][j] == 1)
for(i2 = i1 + 1; i2 <= r; ++ i2)
if(mat[i2][j] == 1)
rez += (long long)(put[dreptmat[i2 - 1][j] - dreptmat[i1][j] - dreptmat[i2 - 1][j - 1] + dreptmat[i1][j - 1]]) * (i2 - i1 + 1);
rez += nr1;
while(rez % 2 == 0 && nr1 > 0)
{
rez = rez >> 1;
-- nr1;
}
if(nr1 == 0)
printf("%lld/1\n", rez);
else
{
printf("%lld/", rez);
printf("%lld\n", put[nr1]);
}
}
return 0;
}