# Cod sursa(job #2730438)

Utilizator Data 26 martie 2021 12:32:47 Boundingbox 0 cpp-64 done Arhiva de probleme 1.33 kb
``````#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin("boundingbox.in");
ofstream cout("boundingbox.out");

vector< vector<int> > mat,scol;
vector<int> fup,fdown;

static void testcase() {
int n,m;
long long nbox=0,barea=0,temp;
char ch;
cin >> n >> m;
mat=vector< vector<int> >(min(n,m)+2,vector<int>(max(n,m)+2));
scol=vector< vector<int> >(min(m,n)+2,vector<int>(max(n,m)+2,0));
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
cin >> ch;
if(n>m)
swap(i,j);
mat[i][j]=ch-'0';
scol[i][j]=scol[i-1][j]+mat[i][j];
if(n>m)
swap(i,j);
}
}
if(n>m)
swap(n,m);
nbox=1;
barea=0;
for(int stcol=1; stcol<=m; stcol++) {
for(int i=1,iscol; i<=n; i++) {
iscol=0;
for(int j=i; j<=n; j++) {
iscol|=mat[j][stcol];
if(iscol==0)
continue;
for(int h=stcol,isrow=0; h<=m; h++) {
if(mat[i][h])
isrow|=1;
if(mat[j][h])
isrow|=2;
if(isrow==3 && scol[j][h]-scol[i-1][h]>0) {
barea+=(long long)(j-i+1)*(long long)(h-stcol+1);
nbox++;
}
}
}
}
}
temp=__gcd(barea,nbox);
cout << barea/temp << "/" << nbox/temp  << '\n';
}

int main() {
int t;
cin >> t;
for(int i=0; i<t; i++)
testcase();
}
``````