Cod sursa(job #1519910)

Utilizator lflorin29Florin Laiu lflorin29 Data 8 noiembrie 2015 00:36:56
Problema Minesweeper Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <bits/stdc++.h>

using namespace std;

const int max_n = 27;
const double mmr = 1e-12;

int N, M, L;
int val[max_n][max_n];
double A[max_n][max_n];
double nec[max_n];

void Init() {
    ifstream cin("minesweeper.in");
    cin >> N >> M;
    N *= M;
    M = 0;
    for(int G = 0; G <= N; ++G)
        for(int S = 0; G + S <= N; ++S)
            val[G][S] = (++M);
    L = ++M;
    M = 1;
    for(int G = 0; G <= N; ++G)
        for(int S = 0; G + S <= N; ++S, ++M) {
            int I = N - S - G;
            A[M][M] = 1;
            if(I == N)
                continue;
            if(G)
               A[M][val[G - 1][S + 1]] -= (1.0 * G) / (1.0 * N);
            if(S)
                A[M][val[G][S - 1]] -= (1.0 * S) / (1.0 * N);
            if(I)
                A[M][val[G + 1][S]] -= (1.0 * I) / (1.0 * N);
            A[M][L] = 1;
        }
}

bool bun(double valu) {
    return abs(valu) > mmr;
}

void Gauss() {
    for(int i = 1; i < L; ++i) {
         if(bun(A[i][i])) {
           for(int j = i + 1 ; j <= L ; ++j)
              A[i][j] /= A[i][i];
            A[i][i] = 1;
         }
         for(int j = i + 1; j < L; ++j) {
            for(int k = i + 1; k <= L; ++k)
                A[j][k] -= (A[j][i] * A[i][k]);
             A[j][i] = 0;
         }
    }
}

void Slv() {
    for(int i = L; i; --i) {
        nec[i] = A[i][L];
        for(int j = i + 1 ; j < L; ++j)
            nec[i] -= A[i][j] * nec[j];
    }
    ofstream("minesweeper.out") << fixed << setprecision(10) << nec[L - 1];
}

int main() {
    Init();
    Gauss();
    Slv();
    return 0;
}