Pagini recente » Cod sursa (job #1031579) | Cod sursa (job #1120702) | Cod sursa (job #753513) | Cod sursa (job #3165619) | Cod sursa (job #2116870)
#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;
}