Pagini recente » Cod sursa (job #1522206) | Cod sursa (job #1395737) | Cod sursa (job #1603069) | Cod sursa (job #2365019) | Cod sursa (job #1230890)
#include <fstream>
#include <vector>
using namespace std;
typedef unsigned long long ui64;
int T, N, M, K;
char a[55][55];
ui64 conf, lim, A;
vector<pair<int, int> > unu;
ifstream fin("boundingbox.in");
ofstream fout("boundingbox.out");
inline void UpdMin(int &var, int val) {
if (val < var)
var = val;
}
inline void UpdMax(int &var, int val) {
if (val > var)
var = val;
}
ui64 Cmmdc(ui64 a, ui64 b) {
if (!b)
return a;
return Cmmdc(b, a % b);
}
int main() {
fin >> T;
while (T--) {
unu.clear();
fin >> N >> M;
for (int i = 0; i < N; ++i)
fin >> a[i];
for (int i = 0; i < N; ++i)
for (int j = 0; j <= M; ++j)
if (a[i][j] == '1')
unu.push_back(make_pair(i, j));
K = static_cast<int>(unu.size());
lim = 1LL << K;
A = 0;
for (conf = 1; conf < lim; ++conf) {
int xmin = 55, xmax = -1, ymin = 55, ymax = -1;
for (int i = 0; i < K; ++i)
if (conf & (1LL << i)) {
UpdMin(xmin, unu[i].first);
UpdMax(xmax, unu[i].first);
UpdMin(ymin, unu[i].second);
UpdMax(ymax, unu[i].second);
}
A += (xmax - xmin + 1) * (ymax - ymin + 1);
}
int cmmdc = Cmmdc(A, lim);
A /= cmmdc;
lim /= cmmdc;
fout << A << "/" << lim << "\n";
}
return 0;
}