Pagini recente » Cod sursa (job #995158) | Cod sursa (job #2236689) | Cod sursa (job #2266624) | Cod sursa (job #2486547) | Cod sursa (job #1230939)
#include <fstream>
#define DIM 55
#define infile "boundingbox.in"
#define outfile "boundingbox.out"
using namespace std;
ifstream f(infile);
ofstream g(outfile);
int kk,ml,Ml,mc,Mc,X,Y,t,m,n;
char ch[DIM];
int a[DIM],A[DIM][DIM];
struct data {
int x;
int y;
}v[DIM];
void back(int k) {
if (k-1 == kk) {
Ml = Mc = 0;
ml = mc = 1000;
bool ok = 0;
for (int i=1; i<=kk; ++i)
if (a[i] == 1) {
Ml = max(Ml, v[i].x);
ml = min(ml, v[i].x);
Mc = max(Mc, v[i].y);
mc = min(mc, v[i].y);
ok = 1;
}
if (!ok)
return;
X += 1LL * (Ml-ml+1)*(Mc-mc+1);
Y ++;
return;
}
a[k] = 1;
back(k+1);
a[k] = 0;
back(k+1);
}
int main () {
f >> t;
while (t--) {
f >> m >> n;
Y = 1; X = 0;kk = 0;
f.get();
for (int i=1; i<=m; ++i) {
f.get(ch, DIM);
for (int j=1; j<=n; ++j) {
A[i][j] = ch[j-1] - '0';
if (A[i][j] == 1) {
v[++kk].x = i;
v[kk].y = j;
}
}
f.get();
}
back(1);
long long XX=X, YY=Y;
while (YY!=0) {
long long r=XX%YY;
XX=YY;
YY=r;
}
X/=XX;
Y/=XX;
g<< X<<"/"<<Y<<"\n";
}
return 0;
}