Cod sursa(job #2730438)

Utilizator cadmium_Voicu Mihai Valeriu cadmium_ Data 26 martie 2021 12:32:47
Problema Boundingbox Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 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();
}