Cod sursa(job #2224100)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 22 iulie 2018 21:06:54
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <bits/stdc++.h>

using namespace std;

int x[50][50];
int s[50][50];

int ins(int x1, int y1, int x2, int y2) {
  return max(0, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}

int main() {
  freopen("boundingbox.in", "r", stdin);
  freopen("boundingbox.out", "w", stdout);

  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m;
    scanf("%d%d", &n, &m);
    long long ans = 0;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= m; ++j) {
        scanf("%1d", &x[i][j]);
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x[i][j];
        ans += x[i][j];
      }
    for (int i = 1; i <= n; ++i)
      for (int j1 = 1; j1 < m; ++j1)
        for (int j2 = j1 + 1; j2 <= m; ++j2)
          if (x[i][j1] + x[i][j2] == 2)
            ans += (j2 - j1 + 1) * (1LL << ins(i, j1 + 1, i, j2 - 1));
    for (int j = 1; j <= m; ++j)
      for (int i1 = 1; i1 < n; ++i1)
        for (int i2 = i1 + 1; i2 <= n; ++i2)
          if (x[i1][j] + x[i2][j] == 2)
            ans += (i2 - i1 + 1) * (1LL << ins(i1 + 1, j, i2 - 1, j));
    for (int i1 = 1; i1 < n; ++i1)
      for (int i2 = i1 + 1; i2 <= n; ++i2)
        for (int j1 = 1; j1 < m; ++j1)
          for (int j2 = j1 + 1; j2 <= m; ++j2) {
            int l1 = ins(i1, j1 + 1, i1, j2 - 1);
            int l2 = ins(i2, j1 + 1, i2, j2 - 1);
            int c1 = ins(i1 + 1, j1, i2 - 1, j1);
            int c2 = ins(i1 + 1, j2, i2 - 1, j2);
            long long e = (1LL << ins(i1 + 1, j1 + 1, i2 - 1, j2 - 1));
            int ar = (i2 - i1 + 1) * (j2 - j1 + 1);
            long long aux = 0;
            for (int i = 0; i < 16; ++i) {
              int a = 0, b = 0, c = 0, d = 0;
              if ((i & 1) && !x[i1][j1])
                continue;
              if ((i & 2) && !x[i1][j2])
                continue;
              if ((i & 4) && !x[i2][j2])
                continue;
              if ((i & 8) && !x[i2][j1])
                continue;
              if ((i & 1) == 0 && (i & 2) == 0)
                a = 1;
              if ((i & 2) == 0 && (i & 4) == 0)
                b = 1;
              if ((i & 4) == 0 && (i & 8) == 0)
                c = 1;
              if ((i & 8) == 0 && (i & 1) == 0)
                d = 1;
              aux += ((1LL << l1) - a) * ((1LL << c2) - b) * ((1LL << l2) - c) * ((1LL << c1) - d);
            }
            ans += aux * ar * e;
          }
    if (ans == 0LL) {
      printf("0/1\n");
    } else {
      long long nr = (1LL << s[n][m]);
      while (nr % 2 == 0 && ans % 2 == 0) {
        nr /= 2;
        ans /= 2;
      }
      printf("%lld/%lld\n", ans, nr);
    }
    memset(s, 0, sizeof(s));
  }

  return 0;
}