# Cod sursa(job #2116870)

Utilizator Data 28 ianuarie 2018 11:30:18 Boundingbox 100 cpp done Arhiva de probleme 1.71 kb
``````#include <fstream>
#include <string>
#include <cstring>

using namespace std;

ifstream fin ("boundingbox.in"); ofstream fout ("boundingbox.out");

const int nmax = 50;

int n, m, cnt1;
bool v[nmax + 1][nmax + 1];
int p2[nmax + 1];
int s[nmax + 1][nmax + 1];
string buff;

void citire () {
fin >> n >> m;

cnt1 = 0;
for (int i = 1; i <= n; ++ i) {
fin >> buff;

for (int j = 1; j <= m; ++ j) {
v[ i ][ j ] = buff[j - 1] - '0';
cnt1 += v[ i ][ j ];
}
}

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

inline long long sp (int a, int b, int x, int y) {
int cnt = s[ x ][ y ] - s[ x ][b - 1] - s[a - 1][ y ] + s[a - 1][b - 1];
return (1LL << cnt) - 1;
}

void solve () {
citire ();

long long ans = 0;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
ans += (1LL << cnt1);

ans -= sp(1, 1, i - 1, m);
ans -= sp(1, j + 1, n, m);
ans -= sp(i + 1, 1, n, m);
ans -= sp(1, 1, n, j - 1);

ans += sp(1, 1, i - 1, j - 1);
ans += sp(1, j + 1, i - 1, m);
ans += sp(i + 1, j + 1, n, m);
ans += sp(i + 1, 1, n, j - 1);

-- ans; /// cazul in care nu iau nimic
}
}

long long fr = (1LL << cnt1);
while (fr > 1 && (ans & 1) == 0) {
fr >>= 1;
ans >>= 1;
}

fout << ans << "/" << fr << "\n";
}

int main () {
int t;
fin >> t;

while (t --) {
solve ();
}

fin.close();
fout.close();
return 0;
}
``````