Cod sursa(job #801552)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 24 octombrie 2012 18:05:43
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <cstdio>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <vector>

using namespace std;

const int MaxN = 405;
const double Eps = 1e-8;

vector<double> A[MaxN];
int Cells, N, M, Variable[MaxN][MaxN];
double Sol[MaxN];

void BuildVariables() {
    for (int Free = 0; Free <= Cells; ++Free)
        for (int Flag = 0; Flag+Free <= Cells; ++Flag)
            Variable[Free][Flag] = M++;
}

void BuildEquations() {
    for (int Free = 0; Free <= Cells; ++Free) {
        for (int Flag = 0; Flag+Free <= Cells; ++Flag, ++N) {
            int Q = Cells-Free-Flag;
            A[N].resize(M+1, 0);
            A[N][Variable[Free][Flag]] = 1;
            if (Q == Cells)
                continue;
            if (Free > 0)
                A[N][Variable[Free-1][Flag+1]] -= (1.0*Free)/(1.0*Cells), A[N][M] += (1.0*Free)/(1.0*Cells);
            if (Flag > 0)
                A[N][Variable[Free][Flag-1]] -= (1.0*Flag)/(1.0*Cells), A[N][M] += (1.0*Flag)/(1.0*Cells);
            if (Q > 0)
                A[N][Variable[Free+1][Flag]] -= (1.0*Q)/(1.0*Cells), A[N][M] += (1.0*Q)/(1.0*Cells);
        }
    }
}

void BuildSystem() {
    BuildVariables();
    BuildEquations();
}

inline void Reduce(vector<double> &L1, vector<double> &L2, double C) {
    for (int i = 0; i <= M; ++i)
        L1[i] += C*L2[i];
}

void Gauss() {
    int i = 0, j = 0;
    while (i < N && j < M) {
        int k;
        for (k = i; k < N && abs(A[k][j]) < Eps; ++k);
        if (k == N) {
            ++j; continue;
        }
        swap(A[i], A[k]);
        for (k = 0; k < N; ++k)
            if (i != k)
                Reduce(A[k], A[i], -A[k][j]/A[i][j]);
        ++i, ++j;
    }
}

void BuildSol() {
    for (int i = 0; i < N; ++i) {
        int j;
        for (j = 0; j < M && abs(A[i][j]) < Eps; ++j);
        if (j < M)
            Sol[j] = A[i][M]/A[i][j];
    }
}

void Solve() {
    BuildSystem();
    Gauss();
    BuildSol();
}

void Read() {
    assert(freopen("minesweeper.in", "r", stdin));
    int R, C; assert(scanf("%d %d", &R, &C) == 2);
    Cells = R*C;
}

void Print() {
    assert(freopen("minesweeper.out", "w", stdout));
    printf("%.8lf\n", Sol[Variable[Cells][0]]);
}

int main() {
    Read();
    Solve();
    Print();
}