Cod sursa(job #1230576)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 18 septembrie 2014 16:29:49
Problema Boundingbox Scor Ascuns
Compilator cpp Status done
Runda Marime 3.93 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long int64;

const char IN_FILE[] = "boundingbox.in";
const char OUT_FILE[] = "boundingbox.out";
const int MAX_D = 8;
const int DX[MAX_D] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int DY[MAX_D] = {0, 1, 1, 1, 0, -1, -1, -1};
const int oo = 0x3f3f3f3f;

int Rows, Columns;
vector< vector<int> > SumBlack;
vector<int> Masks;
pair<int64, int64> Answer;

inline int GetBit(const int mask, const int bit) {
    return (mask >> bit) & 1;
}

inline int64 GCD(int64 x, int64 y) {
    while (y) {
        int64 r = x % y;
        x = y;
        y = r;
    }
    return x;
}

inline int GetBlack(const int x0, const int y0, const int x1, const int y1) {
    if (x0 > x1 || y0 > y1)
        return 0;
    return SumBlack[x1][y1] - SumBlack[x0 - 1][y1] - SumBlack[x1][y0 - 1] + SumBlack[x0 - 1][y0 - 1];
}

void Preprocess() {
    Masks = vector<int>();
    int cx = 1, cy = 1;
    for (int mask = 0; mask < (1 << MAX_D); ++mask) {
        bool map[3][3];
        map[cx][cy] = false;
        for (int d = 0; d < MAX_D; ++d) {
            int x = cx + DX[d], y = cy + DY[d];
            map[x][y] = GetBit(mask, d);
        }
        int minX = oo, maxX = -oo, minY = oo, maxY = -oo;
        for (int x = 0; x < 3; ++x) {
            for (int y = 0; y < 3; ++y) {
                if (map[x][y]) {
                    minX = min(minX, x);
                    maxX = max(maxX, x);
                    minY = min(minY, y);
                    maxY = max(maxY, y);
                }
            }
        }
        if (!(minX <= cx && cx <= maxX && minY <= cy && cy <= maxY))
            Masks.push_back(mask);
    }
}

void Solve() {
    Preprocess();
    int n = Rows * Columns;
    Answer = make_pair(0LL, 1LL << n);
    for (int x = 1; x <= Rows; ++x) {
        for (int y = 1; y <= Columns; ++y) {
            int64 p = 0;
            int black[MAX_D];
            black[0] = GetBlack(1, y, x - 1, y);
            black[1] = GetBlack(1, y + 1, x - 1, Columns);
            black[2] = GetBlack(x, y + 1, x, Columns);
            black[3] = GetBlack(x + 1, y + 1, Rows, Columns);
            black[4] = GetBlack(x + 1, y, Rows, y);
            black[5] = GetBlack(x + 1, 1, Rows, y - 1);
            black[6] = GetBlack(x, 1, x, y - 1);
            black[7] = GetBlack(1, 1, x - 1, y - 1);
            for (const auto &mask: Masks) {
                int64 nowP = 1LL << n;
                for (int d = 0; d < MAX_D; ++d) {
                    if (GetBit(mask, d) == 0)
                        nowP = nowP / (1LL << black[d]);
                    else
                        nowP = (nowP / (1LL << black[d])) * ((1LL << black[d]) - 1);
                }
                p = p + nowP;
            }
            if (GetBlack(x, y, x, y) == 1)
                p = p / 2;
            p = (1LL << n) - p;
            Answer.first = Answer.first + p;
        }
    }
    int64 d = GCD(Answer.first, Answer.second);
    Answer.first /= d;
    Answer.second /= d;
}

void Read(ifstream &cin) {
    cin >> Rows >> Columns;
    SumBlack = vector< vector<int> >(Rows + 2, vector<int>(Columns + 2, 0));
    for (int x = 1; x <= Rows; ++x) {
        string row;
        cin >> row;
        for (int y = 1; y <= Columns; ++y)
            SumBlack[x][y] = int(row[y - 1] - '0');
    }
    for (int x = 1; x <= Rows + 1; ++x)
        for (int y = 1; y <= Columns + 1; ++y)
            SumBlack[x][y] += SumBlack[x - 1][y] + SumBlack[x][y - 1] - SumBlack[x - 1][y - 1];
}

void Print(ofstream &cout) {
    cout << Answer.first << "/" << Answer.second << "\n";
}

int main() {
    ifstream cin("boundingbox.in");
    ofstream cout("boundingbox.out");
    int tests;
    cin >> tests;
    for (; tests > 0; --tests) {
        Read(cin);
        Solve();
        Print(cout);
    }
    cin.close();
    cout.close();
    return 0;
}