Cod sursa(job #2116870)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 28 ianuarie 2018 11:30:18
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <string>
#include <cstring>

using namespace std;

ifstream fin ("boundingbox.in"); ofstream fout ("boundingbox.out");

const int nmax = 50;

int n, m, cnt1;
bool v[nmax + 1][nmax + 1];
int p2[nmax + 1];
int s[nmax + 1][nmax + 1];
string buff;

void citire () {
    fin >> n >> m;

    cnt1 = 0;
    for (int i = 1; i <= n; ++ i) {
        fin >> buff;

        for (int j = 1; j <= m; ++ j) {
            v[ i ][ j ] = buff[j - 1] - '0';
            cnt1 += v[ i ][ j ];
        }
    }

    memset(s, 0, sizeof(s));
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            s[ i ][ j ] = s[i - 1][ j ] + s[ i ][j - 1] - s[i - 1][j - 1] + v[ i ][ j ];
        }
    }
}

inline long long sp (int a, int b, int x, int y) {
    int cnt = s[ x ][ y ] - s[ x ][b - 1] - s[a - 1][ y ] + s[a - 1][b - 1];
    return (1LL << cnt) - 1;
}

void solve () {
    citire ();

    long long ans = 0;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            ans += (1LL << cnt1);

            ans -= sp(1, 1, i - 1, m);
            ans -= sp(1, j + 1, n, m);
            ans -= sp(i + 1, 1, n, m);
            ans -= sp(1, 1, n, j - 1);

            ans += sp(1, 1, i - 1, j - 1);
            ans += sp(1, j + 1, i - 1, m);
            ans += sp(i + 1, j + 1, n, m);
            ans += sp(i + 1, 1, n, j - 1);

            -- ans; /// cazul in care nu iau nimic
        }
    }

    long long fr = (1LL << cnt1);
    while (fr > 1 && (ans & 1) == 0) {
        fr >>= 1;
        ans >>= 1;
    }

    fout << ans << "/" << fr << "\n";
}

int main () {
    int t;
    fin >> t;

    while (t --) {
        solve ();
    }

    fin.close();
    fout.close();
    return 0;
}