Pagini recente » Cod sursa (job #1695652) | Cod sursa (job #2354516) | Cod sursa (job #3190281) | Cod sursa (job #1541214) | Cod sursa (job #1230871)
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int Nmax = 55;
char A[Nmax];
vector< pair<int, int> > points;
int minx = Nmax, maxx = 0, miny = Nmax, maxy = 0;
int ans;
void back(int pos) {
if (pos == int(points.size())) {
if (minx != Nmax)
ans += (maxx - minx + 1) * (maxy - miny + 1);
} else {
int minxs = minx, maxxs = maxx, minys = miny, maxys = maxy;
minx = min(minx, points[pos].first);
maxx = max(maxx, points[pos].first);
miny = min(miny, points[pos].second);
maxy = max(maxy, points[pos].second);
back(pos + 1);
minx = minxs;
maxx = maxxs;
miny = minys;
maxy = maxys;
back(pos + 1);
}
}
int gcd(int a, int b) {
int c;
while (b) {
c = a % b;
a = b;
b = c;
}
return a;
}
int main()
{
freopen("boundingbox.in", "r", stdin);
freopen("boundingbox.out", "w", stdout);
int T;
scanf("%d\n", &T);
while (T--) {
points.clear();
int N, M;
scanf("%d %d\n", &N, &M);
for (int i = 1; i <= N; ++i) {
fgets(A + 1, Nmax, stdin);
for (int j = 1; j <= M; ++j) {
if (A[j] == '1')
points.push_back(make_pair(i, j));
}
}
ans = 0;
back(0);
int p = gcd(ans, 1 << points.size());
printf("%d/%d\n", ans / p, (1 << points.size()) / p);
}
}