# Cod sursa(job #1772815)

Utilizator Data 7 octombrie 2016 00:59:09 Boundingbox 100 cpp done Arhiva de probleme 3.75 kb
``````#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int kMaxN = 55;

int n, m;
int v[kMaxN][kMaxN];
int s[kMaxN][kMaxN];

int getSum(const int Ax, const int Ay, const int Bx, const int By) {
if (Ax <= Bx && Ay <= By) {
return s[Bx][By] - s[Ax - 1][By] - s[Bx][Ay - 1] + s[Ax - 1][Ay - 1];
}
else {
return 0;
}
}

int64_t boundingBox(const int Ax, const int Ay, const int Bx, const int By) {
if (getSum(Ax, Ay, Bx, By) > 0) {
if (Ax != Bx && Ay != By) {
int pCorner[4] = {};
int pEdge[4] = {};
int pInside;

pInside = getSum(Ax + 1, Ay + 1, Bx - 1, By - 1);
pCorner[0] = v[Ax][Ay];
pCorner[1] = v[Bx][Ay];
pCorner[2] = v[Bx][By];
pCorner[3] = v[Ax][By];
pEdge[0] = getSum(Ax, Ay + 1, Ax, By - 1);
pEdge[1] = getSum(Ax + 1, Ay, Bx - 1, Ay);
pEdge[2] = getSum(Bx, Ay + 1, Bx, By - 1);
pEdge[3] = getSum(Ax + 1, By, Bx - 1, By);

int64_t cnt = 0;
for (int i = 0; i < 16; i++) {
int64_t crCnt = 1;
bool edgeCovered[4] = {};
bool goodSet = true;
for (int j = 0; j < 4; j++) {
if ((i >> j) & 1) {
edgeCovered[j] = true;
edgeCovered[(j + 1) & 3] = true;
goodSet &= (pCorner[j] == 1);
}
}
for (int j = 0; j < 4; j++) {
int64_t factor = 1LL << pEdge[j];
if (!edgeCovered[j]) {
factor--;
}
crCnt *= factor;
}
crCnt *= (1LL << pInside) * goodSet;
cnt += crCnt;
}
return cnt;
}
else {
if (Ax == Bx) {
if (v[Ax][Ay] == 0 || v[Ax][By] == 0) {
return 0;
}
else {
return (1LL << getSum(Ax, Ay + 1, Ax, By - 1));
}
}
else {
if (v[Ax][Ay] == 0 || v[Bx][Ay] == 0) {
return 0;
}
else {
return (1LL << getSum(Ax + 1, Ay, Bx - 1, Ay));
}
}
}
}
else {
return 0;
}
}

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

int testCases;
for (scanf("%d", &testCases); testCases > 0; testCases--) {
scanf("%d %d", &n, &m);

memset(s, 0, sizeof s);
memset(v, 0, sizeof v);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%1d", &v[i][j]);
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v[i][j];
}
}

int64_t sa = 0;
for (int Ax = 1; Ax <= n; Ax++) {
for (int Ay = 1; Ay <= m; Ay++) {
for (int Bx = Ax; Bx <= n; Bx++) {
for (int By = Ay; By <= m; By++) {
const int64_t nsub = boundingBox(Ax, Ay, Bx, By);
sa += 1LL * (Bx - Ax + 1) * (By - Ay + 1) * nsub;
}
}
}
}

int64_t num = sa;
int64_t den = (1LL << getSum(1, 1, n, m));
while (!(num & 1) && !(den & 1)) {
num >>= 1;
den >>= 1;
}

printf("%lld/%lld\n", num, den);
}

return 0;
}``````