Cod sursa(job #1230927)

Utilizator cahemanCasian Patrascanu caheman Data 19 septembrie 2014 13:08:26
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 5.18 kb
#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;
}