Cod sursa(job #1479295)

Utilizator vladrochianVlad Rochian vladrochian Data 31 august 2015 00:16:26
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <iomanip>
using namespace std;

const int kMaxN = 25;
const double kEps = 1e-8;

ifstream fin("minesweeper.in");
ofstream fout("minesweeper.out");

int N, M;
int code[kMaxN][kMaxN];
double a[kMaxN * kMaxN][kMaxN * kMaxN];

bool Zero(double d) {
  return (d > -kEps) && (d < kEps);
}

int main() {
  fin >> N >> M;
  N *= M;

  M = 0;
  for (int i = 0; i <= N; ++i)
    for (int j = 0; i + j <= N; ++j)
      code[i][j] = ++M;

  for (int i = 0; i < N; ++i)
    for (int j = 0; i + j <= N; ++j) {
      int k = code[i][j];
      a[k][k] = -1.0;
      a[k][code[i][j + 1]] = double(N - i - j) / N;
      a[k][code[i + 1][j - 1]] = double(j) / N;
      a[k][code[i - 1][j]] = double(i) / N;
      a[k][M + 1] = -1.0;
    }
  a[M][M] = 1.0;

  for (int k = 1; k <= M; ++k) {
    if (Zero(a[k][k])) {
      int i = k + 1;
      while (Zero(a[i][k]))
        ++i;
      swap(a[k], a[i]);
    }
    for (int i = 1; i <= M; ++i) {
      if (i == k) continue;
      double fact = a[i][k] / a[k][k];
      for (int j = 1; j <= M + 1; ++j)
        a[i][j] -= fact * a[k][j];
    }
  }

  fout << setprecision(8) << (a[1][M + 1] / a[1][1]) << "\n";
  return 0;
}