Cod sursa(job #1868118)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 4 februarie 2017 16:28:08
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
//#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

ifstream cin("minesweeper.in");
ofstream cout("minesweeper.out");

const int MAXN = 30;
const double EPS = 1e-7;

int temp[MAXN * MAXN][MAXN * MAXN];
double eq[MAXN * MAXN][MAXN * MAXN];

bool IsZero(double value) {
    if (-EPS < value && value < EPS)
        return true;
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    n *= m;
    m = 0;
    for (int i = 0; i <= n; i++)
        for (int j = 0; i + j <= n; j++) {
            m++;
            temp[i][j] = m;
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; i + j <= n; j++) {
            int k = temp[i][j];
            if (i)
                eq[k][temp[i - 1][j]] = 1.0 * i / n;
            if (j)
                eq[k][temp[i + 1][j - 1]] = 1.0 * j / n;
            eq[k][temp[i][j + 1]] = (1.0 * n - i - j) / n;
            eq[k][k] = eq[k][m + 1] = -1.0;
        }
    eq[n][m] = 1.0;
    for (int i = 1; i <= m; i++) {
        if (IsZero(eq[i][i])) {
            int j;
            for (j = i + 1; j <= m && IsZero(eq[j][i]); j++);
            if (j <= m)
                swap(eq[i], eq[j]);
            else
                continue;
        }
        for (int j = 1; j <= m; j++)
            if (j != i) {
                double value = eq[j][i] / eq[i][i];
                for (int k = 1; k <= m + 1; k++)
                    eq[j][k] -= value * eq[i][k];
            }
    }
    cout << fixed << setprecision(6) << eq[1][m + 1] / eq[1][1] << "\n";
    return 0;
}