Cod sursa(job #1851509)

Utilizator cella.florescuCella Florescu cella.florescu Data 19 ianuarie 2017 20:22:41
Problema Minesweeper Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 25;
const int MAXE = MAXN * MAXN;
const double EPS = 1e-7;

double eq[MAXE][MAXE];
int aux[MAXN][MAXN];

inline double iszero(double value) {
  return (-EPS < value && value < EPS);
}

int main()
{
    double v;
    int n, m, x;
    ifstream fin("minesweeper.in");
    fin >> n >> m;
    fin.close();
    n *= m; m = 0;
    for (int i = 0; i <= n; ++i)
      for (int j = 0; i + j <= n; ++j)
        aux[i][j] = ++m;
    for (int i = 0; i < n; ++i)
      for (int j = 0; i + j <= n; ++j) {
        x = aux[i][j];
        eq[x][aux[i - 1][j]] = 1.0 * i / n;
        eq[x][aux[i + 1][j - 1]] = 1.0 * j / n;
        eq[x][aux[i][j + 1]] = (1.0 * n - i - j) / n;
        eq[x][x] = eq[x][m + 1] = -1.0;
      }
    eq[m][m] = 1.0;
    for (int i = 1; i <= m; ++i) {
      if (iszero(eq[i][i])) {
        for (x = i + 1; x <= m && iszero(eq[x][i]); ++x) {}
        if (x <= m)
          swap(eq[i], eq[x]);
        else
          continue;
      }
      for (x = 1; x <= m; ++x)
        if (x != i) {
          v = 1.0 * eq[x][i] / eq[i][i];
          for (int j = 1; j <= m + 1; ++j)
            eq[x][j] -= v * eq[i][j];
        }
    }
    ofstream fout("minesweeper.out");
    fout << setprecision(6) << fixed << eq[1][m + 1] / eq[1][1] << '\n';
    fout.close();
    return 0;
}