Cod sursa(job #1788017)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 25 octombrie 2016 15:25:16
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#include <iomanip>

using namespace std;

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

const int nmax = 23 * 23 + 10;
const double eps = 1e-8;
int n, nrst;
double ans[nmax + 1];
double a[nmax + 1][nmax + 1];

inline int indice (int i, int j) {
    return i * (n + 1) + j;
}

void interschimba (int x, int y) {
    for (int i = 0; i <= nrst + 1; ++ i) {
        swap(a[ x ][ i ], a[ y ][ i ]);
    }
}

void simplifica (int x, int y) {
    double k = a[ x ][ y ];
    for (int i = y; i <= nrst + 1; ++ i) {
        a[ x ][ i ] /= k;
    }

    for (int i = x + 1; i <= nrst; ++ i) {
        k = a[ i ][ y ];
        for (int j = y; j <= nrst + 1; ++ j) {
            a[ i ][ j ] -= a[ x ][ j ] * k;
        }
    }
}

void gauss() {
    int j = 0;
    for (int i = 0; i <= nrst; ++ i) {
        int x;

        while (j <= nrst) {
            x = i;
            while (x <= nrst && (-eps < a[ x ][ j ] && a[ x ][ j ] < eps)) {
                ++ x;
            }

            if (x <= nrst) {
                break;
            }
            ++ j;
        }

        if (j <= nrst) {
            interschimba(i, x);
            simplifica(i, j);
            ++ j;
        }
    }

    for (int i = nrst; i >= 0; -- i) {
        for (int j = 0; j <= nrst; ++ j) {
            if (a[ i ][ j ] >= eps || a[ i ][ j ] <= -eps) {
                ans[ j ] = a[ i ][nrst + 1];

                for (int k = j + 1; k <= nrst; ++ k) {
                    ans[ j ] -= ans[ k ] * a[ i ][ k ];
                }
                break;
            }
        }
    }
}

int main() {
    int dn, dm;
    fin >> dn >> dm;
    n = dn * dm;

    nrst = indice(n, n);

    for (int i = 0; i <= n; ++ i) {
        for (int j = 0; j <= n - i; ++ j) {
            int k = indice(i, j);
            a[ k ][ k ] = 1;
            if (i - 1 >= 0 && j + 1 <= n)
                a[ k ][ indice(i - 1, j + 1) ] = -1.0 * i / n;
            if (j - 1 >= 0)
                a[ k ][ indice(i, j - 1) ] = -1.0 * j / n;
            if (i + 1 <= n)
                a[ k ][ indice(i + 1, j) ] = -1.0 * (n - i - j) / n;
            a[ k ][nrst + 1] = 1;
        }
    }

    for (int i = 0; i <= nrst + 1; ++ i) {
        a[ 0 ][ i ] = 0;
    }
    a[ 0 ][ 0 ] = 1;

    gauss();

    fout << setprecision( 10 ) << fixed;
    fout << ans[ indice(n, 0) ] << "\n";

    fin.close();
    fout.close();
    return 0;
}