Cod sursa(job #2391657)

Utilizator PetyAlexandru Peticaru Pety Data 29 martie 2019 09:00:35
Problema Minesweeper Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;

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

const double eps = 0.0000001;

int n, m, nr, poz[23][23];
double a[452][452], x[452];

int main()
{
  fin >> n >> m;
  n = n * m;
  for (int i = 0; i <= n; i++)
    for (int j = 0; j + i <= n; j++)
      poz[i][j] = ++nr;
  for(long i = 0; i <= n; i++){
    for(long j = 0; i + j <= n; j++){
      int k = n - i - j;
      a[poz[i][j]][poz[i][j]] = 1.00;
      if(j)
        a[poz[i][j]][poz[i + 1][j - 1]] = (double)-j / n;
      if(k)
        a[poz[i][j]][poz[i][j + 1]] = (double)-k / n;
      if(i)
        a[poz[i][j]][poz[i - 1][j]] = (double)-i / n;
      a[poz[i][j]][nr + 1] = 1.00;
    }
  }
  n = m = nr;
  int i = 1, j = 1;
  while (i <= n && j <= m) {
    int poz = -1;
    for (int k = i; k <= n; k++)
      if (abs(a[k][j]) > eps) {
        poz = k;
        break;
      }
    if (poz == -1) {
      j++;
      continue;
    }

    for (int k = 1; k <= m + 1; k++) {
      swap(a[i][k], a[poz][k]);
    }
    for(int k = j + 1; k <= m + 1; k++)
      a[i][k] = a[i][k] / a[i][j];
    a[i][j] = 1;
    for (int l1 = i + 1; l1 <= n; l1++) {
      for (int c1 = j +1; c1 <= m + 1; c1++)
        a[l1][c1] -= a[l1][j] * a[i][c1];
      a[l1][j] = 0;
    }
    i++;j++;
  }
  for(i = n; i > 0; i--)
    for(j = 1; j <= m; j++)
      if(abs(a[i][j]) > eps) {
        x[j] = a[i][m + 1];
        for(int k = j + 1; k <= m; k++)
          x[j] -= x[k] * a[i][k];
        break;
      }
  fout << fixed << setprecision(5) << x[poz[0][0]];
  return 0;
}