Cod sursa(job #1684781)

Utilizator SmarandaMaria Pandele Smaranda Data 11 aprilie 2016 12:04:05
Problema Minesweeper Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 24;
const double eps = 1.e-14;
int n, nec [N][N];
double A [N * N][N * N], ans [N * N], aux [N * N];

void gauss () {
    int i, j, x, y;
    double z, s;

    i = 1; j = 1;
    while (i <= n && j <= n) {
        for (x = i; x <= n; x ++)
            if (A [x][j] < -eps || A [x][j] > eps)
                break;
        if (fabs (A [x][j]) < eps) { //variabila libera
            j ++;
            ans [j] = 0;
            continue;
        }
        if (i != x) {
            memcpy (aux, A [i], sizeof (A [i]));
            memcpy (A [i], A [x], sizeof (A [x]));
            memcpy (A [x], aux, sizeof (aux));
        }
        z = A [i][j];
        for (y = j; y <= n + 1; y ++)
            A [i][y] = A [i][y] / z;
        for (x = i + 1; x <= n; x ++) {
            z = A [x][j];
            for (y = j; y <= n + 1; y ++)
                A [x][y] = A [x][y] - z * A [i][y];
        }
        ++ i; ++ j;
    }

    for (i = n; i >= 1; i --) {
        x = -1;
        s = 0;
        for (j = 1; j <= n + 1; j ++) {
            if (A [i][j] > eps || A [i][j] < -eps) {
                s = 0;
                for (y = j + 1; y <= n; y ++)
                    s = s + ans [y] * A [i][y];
                ans [j] = A [i][n + 1] - s;
                break;
            }
        }
    }
}

int main () {
    int m, u = 0, k, i, h, j;
    double s;

    freopen ("minesweeper.in", "r", stdin);
    freopen ("minesweeper.out", "w", stdout);

    scanf ("%d%d", &n, &m);
    n = n * m;
    for (i = 0; i <= n; i ++)
        for (j = 0; j + i <= n; j ++)
            nec [i][j] = ++ u;

    for (i = 0; i <= n; i ++)
        for (j = 0; i + j <= n; j ++) {
            if (i + j > n)
                break;
            k = n - i - j;
            h = nec [i][j];
            A [h][h] = 1;
            A [h][nec [i][j - 1]] = -1.0 * (j) / n;
            A [h][nec [i - 1][j + 1]] = -1.0 * (i) / n;
            A [h][nec [i + 1][j]] = -1.0 * (k) / n;

            A [h][u + 1] = 1.0 ;
        }
    for (i = 1; i <= u + 1; i ++)
        A [1][i] = 0;
    A [1][1] = 1.0;
    n = u;
    gauss ();
    printf ("%f\n", ans [u]);
    return 0;
}