Cod sursa(job #1478921)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 29 august 2015 22:58:01
Problema Boundingbox Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <fstream>
#include <cstring>

#define lint long long int
using namespace std;

inline lint gcd (lint a, lint b) {
    if (!b)
        return a;

    lint r = a % b;
    while (r) {
        a = b;
        b = r;
        r = a % b;
    }

    return b;
}

const int NMAX = 55;

int r, c;
char mat[NMAX][NMAX];

int s_part[NMAX][NMAX];

inline void get_precalc() {
    int j;
    for (int i = 1; i <= r; ++ i)
        for (j = 1; j <= c; ++ j)
            s_part[i][j] = (mat[i][j] == '1') + s_part[i][j - 1] + s_part[i - 1][j] - s_part[i - 1][j - 1];
}

inline int first_lines (int lin) {
    return s_part[lin][c];
}

inline int last_lines (int lin) {
    return s_part[r][c] - s_part[lin - 1][c];
}

inline int first_cols (int col) {
    return s_part[r][col];
}

inline int last_cols (int col) {
    return s_part[r][c] - s_part[r][col - 1];
}

inline int lower_left (int lin, int col) {
    return s_part[lin][col];
}

inline int lower_right (int lin, int col) {
    return s_part[lin][c] - s_part[lin][col - 1];
}

inline int upper_left (int lin, int col) {
    return s_part[r][col] - s_part[lin - 1][col];
}

inline int upper_right (int lin, int col) {
    return s_part[r][c] - s_part[r][col - 1] - s_part[lin - 1][c] + s_part[lin - 1][col - 1];
}

lint pow2[55];

inline void precalc_pow2 () {
    pow2[0] = 1;
    for (int i = 1; i <= 54; ++ i)
        pow2[i] = 2 * pow2[i - 1];
}

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

    precalc_pow2();

    int t = 0;
    cin >> t;

    while (t --) {
        cin >> r >> c;

        for (int i = 1; i <= r; ++ i) {
            cin.get();
            cin.get(mat[i] + 1, NMAX);
        }

        get_precalc();

        int ones = 0;
        int i, j;
        for (i = 1; i <= r; ++ i)
            for (j = 1; j <= c; ++ j)
                ones += (mat[i][j] == '1');

        lint ans = 0;
        lint here = 0;
        for (i = 1; i <= r; ++ i)
            for (j = 1; j <= c; ++ j) {
                here = pow2[ones];

                here -= (pow2[first_lines(i - 1)] - 1);
                here -= (pow2[last_lines(i + 1)] - 1);
                here -= (pow2[first_cols(j - 1)] - 1);
                here -= (pow2[last_cols(j + 1)] - 1);
                here += (pow2[lower_left(i - 1, j - 1)] - 1);
                here += (pow2[lower_right(i - 1, j + 1)] - 1);
                here += (pow2[upper_left(i + 1, j - 1)] - 1);
                here += (pow2[upper_right(i + 1, j + 1)] - 1);
                here --;

                ans += here;
            }

        lint d = gcd(ans, pow2[ones]);
        cout << ans / d << '/' << pow2[ones] / d << '\n';
    }

    cin.close();
    cout.close();
    return 0;
}