Cod sursa(job #2730456)

Utilizator cadmium_Voicu Mihai Valeriu cadmium_ Data 26 martie 2021 13:01:41
Problema Boundingbox Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <algorithm>


using namespace std;

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

int mat[50][50];

static void testcase() {
  int n,m;
  char ch;
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      cin >> ch;
      mat[i][j]=ch-'0';
    }
  }
  int area=0,nbox=1;
  for(int x1=0; x1<n; x1++) {
    for(int x2=0; x2<n; x2++) {
      for(int y1=0; y1<m; y1++) {
        for(int y2=0,maxx,maxy,minx,miny; y2<m; y2++) {
          maxx=maxy=-1;
          miny=minx=51;
          for(int i=x1; i<=x2; i++) {
            for(int j=y1; j<=y2; j++) {
              if(mat[i][j]==1) {
                maxx=max(maxx,i);
                minx=min(minx,i);
                maxy=max(maxy,j);
                miny=min(miny,j);
              }
            }
          }
          if(maxx==x2 && maxy==y2 && minx==x1 && miny==y1) {
            nbox++;
            area+=(x2-x1+1)*(y2-y1+1);
          }
        } 
      }
    }
  }
  cout << area/__gcd(nbox,area) <<'/'<< nbox/__gcd(nbox,area) <<'\n'; 
}

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