# Cod sursa(job #2209986)

Utilizator Data 5 iunie 2018 13:11:59 Boundingbox 100 cpp done Arhiva de probleme 1.8 kb
``````#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAXN = 50;

char mat[MAXN + 1][MAXN + 1];
int sp[MAXN + 1][MAXN + 1];

inline int get(int l1, int c1, int l2, int c2) {
if(l1 > l2 || c1 > c2)
return 0;
return sp[l2][c2] - sp[l1 - 1][c2] - sp[l2][c1 - 1] + sp[l1 - 1][c1 - 1];
}

inline ll gcd(ll a, ll b) {
ll r;
while(b > 0) {
r = a % b;
a = b;
b = r;
}
return a;
}

int main() {
FILE *fi, *fout;
int t, i, j, n, m;
fi = fopen("boundingbox.in" ,"r");
fout = fopen("boundingbox.out" ,"w");
fscanf(fi,"%d " ,&t);
while(t > 0) {
t--;
fscanf(fi,"%d %d " ,&n,&m);
for(i = 1; i <= n; i++) {
fscanf(fi,"%s " ,mat[i] + 1);
for(j = 1; j <= m; j++) {
mat[i][j] -= '0';
sp[i][j] = sp[i - 1][j] + sp[i][j - 1] + mat[i][j] - sp[i - 1][j - 1];
}
}
ll a = 0, b = (1LL << sp[n][m]);
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
a += (1LL << get(1, 1, i - 1, m));
a += (1LL << get(1, 1, n, j - 1));
a += (1LL << get(1, j + 1, n, m));
a += (1LL << get(i + 1, 1, n, m));
a -= (1LL << get(1, 1, i - 1, j - 1));
a -= (1LL << get(1, j + 1, i - 1, m));
a -= (1LL << get(i + 1, 1, n, j - 1));
a -= (1LL << get(i + 1, j + 1, n, m));
a++;
//printf("%lld " ,a);
}
}
a = (1LL * n * m * (1LL << sp[n][m])) - a;
ll aux = gcd(a, b);
a /= aux;
b /= aux;
fprintf(fout,"%lld/%lld\n" ,a,b);
}
fclose(fi);
fclose(fout);
return 0;
}

``````