Cod sursa(job #2224132)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 23 iulie 2018 00:04:52
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 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 nr[10];

int msk[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 12, 16, 20, 24, 28, 32, 48, 64, 65, 80, 96, 112, 128, 129, 192, 193};

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];
      }
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        nr[0] = ins(1, 1, i - 1, j - 1);
        nr[1] = ins(1, j, i - 1, j);
        nr[2] = ins(1, j + 1, i - 1, m);
        nr[3] = ins(i, j + 1, i, m);
        nr[4] = ins(i + 1, j + 1, n, m);
        nr[5] = ins(i + 1, j, n, j);
        nr[6] = ins(i + 1, 1, n, j - 1);
        nr[7] = ins(i, 1, i, j - 1);
        nr[8] = x[i][j];
        long long aux = 1;
        for (int k = 0; k < 9; ++k)
          aux *= (((1LL << nr[k]) - 1) + 1);
        for (int k = 0; k < 25; ++k) {
          long long aux1 = 1;
          for (int t = 0; t < 9; ++t)
            if (msk[k] & (1 << t))
              aux1 *= ((1LL << nr[t]) - 1);
            aux -= aux1;
        }
        ans += aux;
      }
    }
    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;
}