Cod sursa(job #2224126)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 22 iulie 2018 23:20:10
Problema Boundingbox Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 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 sus[] = {1, 1, 1, 1, 0, 0, 0, 1, 1};
int jos[] = {0, 0, 0, 1, 1, 1, 1, 1, 1};
int st[] = {1, 1, 0, 0, 0, 1, 1, 1, 1};
int dr[] = {0, 1, 1, 1, 1, 1, 0, 0, 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];
      }
    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];
        for (int k = 0; k < 512; ++k) {
          long long aux = 1;
          int a = 0, b = 0, c = 0, d = 0;
          for (int t = 0; t < 9; ++t)
            if (k & (1 << t)) {
              aux *= ((1LL << nr[t]) - 1);
              a |= sus[t];
              b |= jos[t];
              c |= st[t];
              d |= dr[t];
            }
            if (a + b + c + d == 4)
              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;
}