Pagini recente » Cod sursa (job #2678409) | Cod sursa (job #443137) | Cod sursa (job #2211203) | Cod sursa (job #1992255) | Cod sursa (job #1230765)
#include <fstream>
using namespace std;
const int MAX_N = 52;
int T, N, M;
int A[MAX_N][MAX_N], S[MAX_N][MAX_N], pow2[62];
char s[MAX_N + 5];
int countOnes(int x1, int y1, int x2, int y2) {
if(x1 > x2 || y1 > y2)
return 0;
return S[x2][y2] - S[x2][y1 - 1] - S[x1 - 1][y2] + S[x1 - 1][y1 - 1];
}
long long gcd(long long a, long long b) {
while(b) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
int main() {
ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
s[0] = ' ';
pow2[0] = 1;
for(int i = 1; i <= 60; ++i)
pow2[i] = pow2[i - 1] * 2;
f >> T;
for(int t = 1; t <= T; ++t) {
f >> N >> M;
for(int i = 1; i <= N; ++i) {
f >> (s + 1);
for(int j = 1; j <= M; ++j)
A[i][j] = s[j] - '0';
}
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
S[i][j] = A[i][j] + S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1];
long long a = 0, b = 0;
for(int x1 = 1; x1 <= N; ++x1)
for(int x2 = x1; x2 <= N; ++x2)
for(int y1 = 1; y1 <= M; ++y1)
for(int y2 = y1; y2 <= M; ++y2) {
int cntX1 = countOnes(x1, y1, x1, y2),
cntX2 = countOnes(x2, y1, x2, y2),
cntY1 = countOnes(x1, y1, x2, y1),
cntY2 = countOnes(x1, y2, x2, y2),
total = countOnes(x1 + 1, y1 + 1, x2 - 1, y2 - 1);
if(!cntX1 || !cntX2 || !cntY1 || !cntY2)
continue;
long long now = 0;
now = (pow2[cntX1] - 1) * (pow2[cntY1] - 1);
if(x1 != x2)
now *= (pow2[cntX2] - 1);
if(y1 != y2)
now *= (pow2[cntY2] - 1);
now *= pow2[total];
if(A[x1][y1])
now -= pow2[cntX1 - 1] + pow2[cntY1 - 1] - 2;
if(A[x1][y2])
now -= pow2[cntX1 - 1] + pow2[cntY2 - 1] - 2;
if(A[x2][y1] && x2 != x1)
now -= pow2[cntX2 - 1] + pow2[cntY1 - 1] - 2;
if(A[x2][y2] && x2 != x1 && y2 != y1)
now -= pow2[cntX2 - 1] + pow2[cntY2 - 1] - 2;
a += now * (x2 - x1 + 1) * (y2 - y1 + 1);
}
b = pow2[countOnes(1, 1, N, M)];
int d;
do {
d = gcd(a, b);
a /= d;
b /= d;
} while (d != 1);
g << a << "/" << b << "\n";
}
f.close();
g.close();
return 0;
}