Cod sursa(job #1230939)

Utilizator till.lindemannTill Lindemann till.lindemann Data 19 septembrie 2014 13:18:40
Problema Boundingbox Scor 20
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.51 kb
#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;
}