Pagini recente » Cod sursa (job #2619835) | Cod sursa (job #243411) | Cod sursa (job #1048390) | Cod sursa (job #2883734) | Cod sursa (job #1478921)
#include <fstream>
#include <cstring>
#define lint long long int
using namespace std;
inline lint gcd (lint a, lint b) {
if (!b)
return a;
lint r = a % b;
while (r) {
a = b;
b = r;
r = a % b;
}
return b;
}
const int NMAX = 55;
int r, c;
char mat[NMAX][NMAX];
int s_part[NMAX][NMAX];
inline void get_precalc() {
int j;
for (int i = 1; i <= r; ++ i)
for (j = 1; j <= c; ++ j)
s_part[i][j] = (mat[i][j] == '1') + s_part[i][j - 1] + s_part[i - 1][j] - s_part[i - 1][j - 1];
}
inline int first_lines (int lin) {
return s_part[lin][c];
}
inline int last_lines (int lin) {
return s_part[r][c] - s_part[lin - 1][c];
}
inline int first_cols (int col) {
return s_part[r][col];
}
inline int last_cols (int col) {
return s_part[r][c] - s_part[r][col - 1];
}
inline int lower_left (int lin, int col) {
return s_part[lin][col];
}
inline int lower_right (int lin, int col) {
return s_part[lin][c] - s_part[lin][col - 1];
}
inline int upper_left (int lin, int col) {
return s_part[r][col] - s_part[lin - 1][col];
}
inline int upper_right (int lin, int col) {
return s_part[r][c] - s_part[r][col - 1] - s_part[lin - 1][c] + s_part[lin - 1][col - 1];
}
lint pow2[55];
inline void precalc_pow2 () {
pow2[0] = 1;
for (int i = 1; i <= 54; ++ i)
pow2[i] = 2 * pow2[i - 1];
}
int main()
{
ifstream cin("boundingbox.in");
ofstream cout("boundingbox.out");
precalc_pow2();
int t = 0;
cin >> t;
while (t --) {
cin >> r >> c;
for (int i = 1; i <= r; ++ i) {
cin.get();
cin.get(mat[i] + 1, NMAX);
}
get_precalc();
int ones = 0;
int i, j;
for (i = 1; i <= r; ++ i)
for (j = 1; j <= c; ++ j)
ones += (mat[i][j] == '1');
lint ans = 0;
lint here = 0;
for (i = 1; i <= r; ++ i)
for (j = 1; j <= c; ++ j) {
here = pow2[ones];
here -= (pow2[first_lines(i - 1)] - 1);
here -= (pow2[last_lines(i + 1)] - 1);
here -= (pow2[first_cols(j - 1)] - 1);
here -= (pow2[last_cols(j + 1)] - 1);
here += (pow2[lower_left(i - 1, j - 1)] - 1);
here += (pow2[lower_right(i - 1, j + 1)] - 1);
here += (pow2[upper_left(i + 1, j - 1)] - 1);
here += (pow2[upper_right(i + 1, j + 1)] - 1);
here --;
ans += here;
}
lint d = gcd(ans, pow2[ones]);
cout << ans / d << '/' << pow2[ones] / d << '\n';
}
cin.close();
cout.close();
return 0;
}