Pagini recente » Cod sursa (job #2935542) | redsnow_3 | Cod sursa (job #1817280) | Cod sursa (job #2990154) | Cod sursa (job #1230785)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#define x first
#define y second
#define MLT (1<<30)
using namespace std;
typedef pair<int,int> per;
int t,n,m,sum;
int cmmdc(int a,int b) {
for(int c;b;c=a%b,a=b,b=c);
return a;
}
int main()
{
ifstream f("boundingbox.in");
ofstream g("boundingbox.out");
for(f>>t;t--;) {
f>>n>>m;
vector<per> ones; sum=0;
for(int i=0; i<n; ++i) {
string s; f>>s;
for(int j=0; j<m; ++j) if(s[j]=='1') ones.push_back(make_pair(i,j));
}
int l=(1<<ones.size());
for(int s=1; s<l; ++s) {
int xmi=MLT,xma=-MLT,ymi=MLT,yma=-MLT;
for(int i=0; i<ones.size(); ++i) if(s&(1<<i)) {
xmi=min(xmi,ones[i].x); xma=max(xma,ones[i].x);
ymi=min(ymi,ones[i].y); yma=max(yma,ones[i].y);
}
//cerr<<xmi<<' '<<xma<<' '<<ymi<<' '<<yma<<'\n';
sum+=(xma-xmi+1)*(yma-ymi+1);
}
int cm=cmmdc(sum,l);
g<<sum/cm<<'/'<<l/cm<<'\n';
}
return 0;
}